带嵌套 if 语句的 while 循环的 Big-O 运行时

Question

我正在尝试确定这些代码片段的大 O 表示法：

#1:

public static void printProducts (int n) {
    int a = 0; // O(1)
    int b = n; // O(1)

    // O(n)?
    while (a < b){
        // O(?) This if is checked n times, but how many times is it ran?
        if (a * b == n) { 
            System.out.println( a + "*" + b + "=" + a*b ); // O(1)
            a++;                                           // O(1)
            b--;                                           // O(1)
        }
        else if ( a * b > n ) {
            b--;                                           // O(1)
        }
        else if ( a * b < n ) {
            a++;                                           // O(1)
        }
    }
}

#2:

public static void printProducts2 (int n) {
        int a = 1; // O(1)
        int b = n; // O(1)
    
        // O(log n)
        while (a < b){
            if (a * b == n) {
                System.out.println( a + "*" + b + "=" + a*b ); // O(1)
                a++;                                           // O(1)
                b--;                                           // O(1)
            }
            else { 
                if ( a * b > n ) {
                    b = n/a;                                   // O(log n)
                }
                else if ( a * b < n ) {
                    a++;                                       // O(1)
                }
            }
        }
    }

我得出结论，第一个代码的大 O 表示法是 O(n)，第二个代码是 O(log n)，但我不确定它是否正确。我走在正确的轨道上吗？

在问我自己的问题之前，我曾尝试查看问题，但我不太明白它在这里如何应用。

Answer 1

分别为 O(n) 和 O(sqrt(n))。

第一个确实是O(n)。您正确地说 while 循环运行 O(n) 次，并且循环内的所有内容都是恒定时间*，因此 if 条件成立的频率并不重要。

第二个更有趣。您正确地指出 b 的更快减少使函数不那么复杂。事实上，这个函数所做的是逐步增加 a，然后将 b 设置为适当的值，使得 a*b==n，如果 b 存在的话。这意味着 b 只能在 a 发生变化时发生变化，因此至少在进入循环的一半时间内，a 会发生变化。也就是说，每次增加 a.

都会进入循环次数恒定的次数

现在我们只需要计算出 a 增加的频率。当 a > b 时循环停止。因为 b 等于 n/a，这意味着当 a 大于 n 的平方根时循环停止。因此，函数在 O(sqrt(n)).

* 实际上，除法、乘法和比较数字所花费的时间可以随数字的大小而变化，但我们暂时忽略它，因为这似乎不是问题的重点.

带嵌套 if 语句的 while 循环的 Big-O 运行时

Big-O runtime of while-loop with nesten if-statements

java

big-o

runtime

time-complexity

分别为 O(n) 和 O(sqrt(n))。