如何通过循环内的递归调用计算算法的阶数

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)，而且example的顺序要以max为准。

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

Answer 1

while 循环将在 log(max) 中运行。循环的每次迭代都会运行 in 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).

How to calculate the order of an algorithm with recursive calls inside a loop