计算特异性算法的重大复杂性

Question

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

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)似乎是复杂性日志（n）。但是，循环的内部复杂性是什么？

Answer 1

内环为o（i）。如果您考虑其执行的步骤，它将在第一次运行中进行4，第二次运行8，第三名16 ...直到到达n。如果您认为n是2的力量，可以使数学更容易，那么4 8 16 ... n/4 n/2 n ...将为＆lt; = 2n。总的来说，您的算法是o（n）。

Answer 2

首先，请注意，您有一个内置的counter，它将准确记录运行多少迭代。您对该因素的实验在哪里？随着n增加到非常大的数字，counter如何反应？用经验的简而言之，这就是复杂性的定义。

考虑您的循环，而不仅仅是标题声明。全循环控制是

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

等效是

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

因此，您的内部循环确实是 O（log2（n））。

在内部循环中，x从未使用；您可以完全删除该计算。循环所做的就是计算迭代的数量。

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