递归关系和时间复杂度

Question

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

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

Answer 1

当我们处理像Big-Oh，Omega和Theta这样的渐近符号时，我们不考虑常量。毫无疑问，你的时间复杂性会变得如此

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

但是如果你加上这个正在减少的GP系列，你会得到精确的答案等于c * n，其中c将是一些大于1的常数。但是在我前面所说的渐近符号中，常数无关紧要，因此c的值是否为2或50或100或10000或任何东西，它只是O（n）。

另一件事，尽量不要使用Master的定理来解决递归关系，并使用递归树方法，因为它是纯粹的概念，并将帮助您构建您的概念，并可以在每种情况下使用。师父定理就像捷径，也有局限性。