关于时间复杂度示例的问题

问题描述 投票:0回答:1

我是新程序员,最近正在学习数据结构和算法。目前,我无法理解Geeks for Geeks提供的时间复杂度示例,非常感谢您的建议

这里是链接:https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/我们可以在上面的链接中引用第(1)和(2)部分

   // 1st piece of code  
   for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

   // 2nd piece of code: and c is a constant  
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

我不知道为什么第二段代码具有O(N)而第一段代码具有O(1)仅仅是因为第二段代码增加了c,但是第一段代码也增加了一个常数(也就是一个) 。如果可能的话,有人可以建议我可以阅读的任何资源,以便我可以更好地理解时间复杂度吗?最近,我在HackerRank上进行了一些练习,我的很多程序不能仅因为它们运行缓慢而无法通过所有测试用例:)

time-complexity
1个回答
0
投票

复杂度分析的底线是在输入的大小和给定输入的情况下算法将执行的近似操作数之间的关系。您提供的链接使用Big-Oh(算法的操作数上限)。总之,Big-Oh可以定义为:

O(g(n)) = { f(n): there exist positive constants c and n0
          such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

第一个循环执行恒定数量的迭代,与输入大小无关。因此,f(n)-表示算法针对大小为n的输入执行的操作数的函数-受常数的影响。因此,您可以找到另一个常数c,该常数乘以1(g(n))时,其值将始终大于f(n)。在图形中,您会看到f(n)为一条水平线(它是一个常数-不会随N改变)。

另一方面,第二个循环取决于N的大小,因为它确定循环何时结束。因此,您无法找到可以乘以1(g(n))的常数,因此该常数将始终大于f(n)。

关于这个问题,有一些很好的MOOC。例如:-https://www.coursera.org/learn/analysis-of-algorithms-https://www.courses.com/university-of-new-south-wales/cs2-data-structures-and-algorithms/1

https://www.coursera.org/learn/analysis-of-algorithms

© www.soinside.com 2019 - 2024. All rights reserved.