对 Big-O 表示法感到困惑

Question

好吧，我有一个简单的问题要问所有正在准备回答一个简单问题的程序员。

在我的计算机科学 II 课上，我们将学习 Big-Oh 表示法，我已经记下了大部分内容，但我仍然对示例的一些语义感到困惑。

这里的一切都是用 Java 编写的。

我的教授在课堂上给了我们这些例子，但幸运的是，我没有写下答案。

a)

int count = 0; 
    for (int i = 1; i <= n; i++) 
        for (int j = n; j > 1; j-­--­-) 
            for (int k = 1; k < n; k = k + 2) 
                count++;

b)

int count = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = n; j > 1; j-­--­-) 
        for (int k = 1; k < 1000; k = k + 2) 
            count++;

c)

int count = 0; 
    for (int i = 1; i <= 1000000; i++) 
        for (int j = i; j > 500; j-­--­-) 
            for (int k = 1; k < 10500; k = k + 2) 
                count++;

d)

int count = 0; 
int j = 1; 
for (int i = 1; i < n; i++) { 
        while (j < n) { 
            j++;
            count++; 
        } 
        j = 1; 
    }

e)

int count = 0; 
int i = n; 
while (i > 1) 
{ 
    count++; i = i / 2; 
}

好吧，这是我的答案/思考过程：

a) N * N * (N / 2) = N^3/2，全部简化为 O(N^3) 表示法

b ) N * N * 500，全部简化为 O(N^2)

c) 这是我最困惑的一个，因为你有三个 for 循环，但所有循环都迭代了确切的次数。我的猜测是 O(1)，但我不知道...

d) N * N = N^2，所以 O(N^2)

e) 每次除以一半，所以 log(n) = O( log(n)) [均为基数 2]

那么任何人都可以检查我的思维过程并看看我是否遗漏了什么？提前非常感谢！

Answer 1

是的，(C) 是 O(1)，因为它都是常数。

Answer 2

在所有这些示例中，count 对于每个工作单元都会递增一次。如果你能弄清楚count和n之间的关系，那么你就知道了程序的渐近顺序。

很高兴你把事情解决了。下一步是根据实际情况检查您的计算。针对不同的 n 值运行代码，打印出 count，然后根据实际数据检查您的工作。