计算特定算法的大O复杂度

Question

我目前正在努力寻找以下源代码片段的大 O 复杂性：

private static long algo1(long n){
    long counter = 0;
    long i = 1;
    long x = 1;
    while(i < n){
        long a = 4*i;
        for (long j = a; j >= 1; j--) {
            x = x+j;
            counter++;
        }
        i = a/2;
    }
    return counter;
}

在我看来，外部 while(i < n) 的复杂度为 log(n)。但是内部for循环的复杂度是多少？

Answer 1

内循环是 O(i)。如果您考虑它执行的步骤，它将在第一个运行上执行 4 个，第二个执行 8 个，第三个执行 16 个……直到达到 n。如果您认为 n 是 2 的幂以使数学更容易一些，则 4 + 8 + 16 + ... + n/4 + n/2 + n ... 将 <= 2n。所以总而言之，你的算法是 O(n).

Answer 2

首先，请注意您有一个 built-in counter，它将准确记录运行的迭代次数。你对那个因素的实验在哪里？当 n 增加到非常大的数字时，counter 会如何反应？简而言之，这就是复杂性的定义。

考虑您的 loop，而不仅仅是 header 语句。整个循环控制是

i = 1
while i < n
    ...
    i *= 2    // i = 4*i / 2

相当于

for (i = 1; i < n; i *= 2)

因此，您的内部循环确实是 O( log2(n) ).

在内循环中，从不使用x；您可以完全放弃该计算。循环所做的只是计算迭代次数。

用n的各种值调用例程；打印结果。

计算特定算法的大O复杂度

Calculate big O complexity of specific algorithm

algorithm

complexity-theory

big-o

time-complexity