如何计算循环内递归调用的算法顺序

Question

我一直在做一些计算成本递归算法的例子，这些算法是在循环里面的，这个让我很疑惑，怎么计算呢？

int example(int max) {
    int i  =  1;
    double x  =  0.0;

    while ( i <= max ) {
        x  =  calculate (x , i);
        i  = 2 ∗ i ;
    }
}

我们知道calculate(int x，int i)是O(i)的，例子的顺序应该是基于max。

一个更简单的例子是同样的代码，用for(int i = 1; i <= max; i++)循环，这将使例子上的顺序为O(max^2)，但在这种情况下，i在每次调用时都要乘以2。这种情况下如何计算成本呢？

Answer 1

while 循环将在 log(max). 循环的每次迭代将以 O(i). 因此，总的时间复杂度为 。

T(max) = O(1 + 2 + 2^2 + ... + 2^{log(max)}) = O(2^{log(max) + 1} - 1)

我们知道 2^{log(max)} = max, T(max) = Theta(max).