如何找到算法的时间复杂度

Question

我应该找出这个算法的时间复杂度，但我不确定我是否完全理解如何去做。谁能帮我解释一下如何找到这个算法的 big-tome 复杂性，用大 O 表示法？

给定一个整数数组 A[1,...,n]

i := 1;
x := 0;
while(i <= n)
    j := 1;
    x := x+A[i];
    while(j > 0)
        y := x/(2*j);
        j = j/2; //Assume here that this returns the floor of the quotient
    i = 2*i;
return y;

我要的是关于如何解决此类问题的解释。

Answer 1

由于j在内循环开始之前总是设置为1，然后在整数除法时变为0，所以内循环总是运行一度。结果代码可以这样看，去掉了对变量j的操作，不影响整体的时间复杂度：

i := 1;
x := 0;
while(i <= n)
    x := x+A[i];
    y := x/2;
    i = 2*i;
return y;

由于 i 将遍历 2 的幂序列，剩余的循环将迭代 1+floor(log(n)) 次。

假设算术运算在常数时间内执行，时间复杂度为O(log n).

如何找到算法的时间复杂度

How to find time complexty of algorithm

algorithm

runtime

pseudocode