algorithm - 递归关系和时间复杂度

Question

以下伪代码的递归关系和时间复杂度是多少？

temp = 1 
repeat 
    for i=1 to n 
        temp = temp +1 
    n=n/2
until n>=1

标签： algorithmtime-complexitycomplexity-theory

Answer 1

当我们处理像 Big-Oh、Omega 和 Theta 这样的渐近符号时，我们不考虑常数。毫无疑问，您的时间复杂度会像

    n + n/2 + n/4 + ... + 1

但是如果你加上这个递减的 GP 系列，你会得到等于 c*n 的确切答案，其中 c 将是大于 1 的常数。但正如我之前所说的，在渐近符号中，常数并不重要，所以 c 的值是否为 2或 50 或 100 或 10000 或任何东西，它只会是 O(n)。

另一件事，尽量不要使用大师定理来解决递归关系并使用递归树方法，因为它是纯概念的，将帮助你建立你的概念，并且可以在任何情况下使用。硕士定理就像捷径一样，也有局限性。