为什么以下代码的 Big O Notations 是这样的？

Question

问题一

我的答案：1 + n^2 * n = n^3

正确答案：O(n)

void f(int n) {
    if (n<1000000)
         return 0;
    for (int i=0; i<(n*n); i++)
         return f(n-1);
}

问题二

我的答案：n * n * logn = n^2*logn

正确答案：O(n^3)

int f(int n) {
    for (int i=1; i< (n/2); i++) 
        for(double j =0; j <100; j+= (100.0/n) 
              doSomething (n/2); //doSomething(m) has time complexity of O(m)
    return 0;
}

问题三

我的答案：1 + n * (logn + 1) = O(nlogn)

正确答案：O(logn)

int f(n) {
    if (n<1) return;
    g(n-1); 
}

void g(n) {
    f(n/2) 
    doOne(); // doOne has time complexity O(1)
}

Answer 1

问题 1

void f(int n) {
    if (n<1000000)
         return 0;
    for (int i=0; i<(n*n); i++)
         return f(n-1);
}

for循环根本不循环，因为内容是return语句，所以你最多有一个循环迭代。这意味着您可以将此代码简化为：

void f(int n) {
    if (n<=0)
         return 0;
    return f(n-1);
}

（针对 O(n) 分析进行了简化）

这里你明白为什么是O(n)因为它在递归停止条件之前一直在倒计时。当你用 f(5*10^300);

之类的东西调用它时，n<100000 有一个 "high" 值检查这一事实并不重要

问题 2

int f(int n) {
    for (int i=1; i< (n/2); i++) 
        for(double j =0; j <100; j+= (100.0/n) 
              doSomething (n/2); //doSomething(m) has time complexity of O(m)
    return 0;
}

关于 O(n) 分析你可以简化一些行：

for (int i=1; i< (n/2); i++)

这可以简化为：

for (int i=1; i<n; i++)

因此它是O(n)，正如您已经识别的那样。

for(double j =0; j <100; j+= (100.0/n)

这可以简化为：

for(double j =0; j <1; j+= (1.0/n)    (divided by 100)
for(double j =0; j <n; j+= 1.0)       (multiplied by n)

再一次，一个简单的 O(n) 循环。

doSomething (n/2);

根据定义，这是一个 O(n) 语句。

所以你总共有 O(n)*O(n)*O(n)，即 O(n^3)。

问题 3

int f(n) {
    if (n<1) return;
    g(n-1); 
}

void g(n) {
    f(n/2) 
    doOne(); // doOne has time complexity O(1)
}

不确定您是如何在此处获得 O(n*log(n)) 的，因为并非每个 n 值都经过检查。事实上，您从 n 开始，步骤是 n/2、n/4、n/8、n/16、n/32、n/64、 n/128, ... 并且在某个时候您达到了终止条件 if (n<1)。这是一个简单的 O(log(n)) 循环。

为什么以下代码的 Big O Notations 是这样的？

Why are the Big O Notations for the following codes like this?

big-o

问题一

问题二

问题三

问题 1

问题 2

问题 3