如何在循环中使用递归调用计算算法的顺序

Question

我一直在做一些计算循环内部成本递归算法的例子，这个让我想知道如何计算它。

int example(int max) {
int i  =  1;
double x  =  0.0;
while ( i <= max ) {
x  =  calculate (x , i);
i  = 2 ∗ i ;
}
}

我们知道计算(int x，int i(是O(i(，并且示例的顺序应该基于max。

一个更简单的例子是具有 for(int i = 1; i <= 最大值;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)} = maxT(max) = Theta(max)。