判断伪代码中方法的大O运行时间，求验证解法正确性

伪代码 #

Static void doIt (int n ) {
    int i;      // 1 operations
    int j; ← (2 x n)    // 1 operations
    while loop (j > 0) {    // n operations 
        i; ← n          // (n+1) operations
            while loop ( i>= 1) {   // (n*n) operations
                i;   ← i/2          // sqrt (n) operations
            }
            j; ← j -1           // (n+1) operations
     }
}

Static int myMethod (int n) {
    sum;  ←     // 1 operations
    for i ← 1 to n {    // (n operations)
        sum = sum + doIt(i);    // (n+1) operations
    }
    return 1;   // a 
}

你的解法 #

T(n) = 1 + 1 + n + (n+1) + (n*n) + sqrt(n) + 1 + n + (n+1) + a = n^2 + 5n + 5 + sqrt(n)  
big-o complexity = O(n^2)

解法错误分析与正确推导 #

1. doIt(n) 的时间复杂度计算错误 #

• 外层while循环：j初始为2n，每次减1直到j≤0，循环次数是2n次，属于O(n)级别。
• 内层while循环：i初始为n，每次执行i = i/2，直到i<1。这个过程的循环次数是log₂n次（每次数值减半，直到趋近于0），属于O(log n)级别。
• 因此doIt(n)的时间复杂度是外层循环次数 × 内层循环次数：O(n × log n)，你统计的n²、sqrt(n)等项完全不符合实际循环逻辑。

2. myMethod(n) 的时间复杂度完全错误 #

myMethod从i=1到i=n循环调用doIt(i)，总时间是对k从1到n的doIt(k)时间复杂度求和，即：
$$\sum_{k=1}^n O(k \log k)$$
这个求和的渐近上界是O(n² log n)，因为当n足够大时，求和式的主导项是n² log n，远大于你计算的n²级别。

3. 操作次数统计逻辑错误 #

你直接把两个方法的所有操作次数简单相加，忽略了myMethod循环调用doIt的嵌套关系，也错误估计了内层循环的执行次数。大O复杂度关注的是渐近增长趋势，不需要统计单个赋值这类常数级操作，核心是循环的嵌套次数和规模。

最终结论 #

你的解法完全错误，正确的时间复杂度：

• doIt(n)：O(n log n)
• myMethod(n)：O(n² log n)

内容的提问来源于stack exchange，提问作者struggling-cs-student