algorithm - 条件语句的时间复杂度

Question

<分区>

Answer 1

假设第二个while循环应为 while j<=n ，时间复杂度为:

O(n)

而决定因素正是 k 上的循环。

我们有:

i=1
while i<=n
    j=1
    while j<=n
        if i==j
            k=1
            while k<=j
                k+=1
                print("hello")
        else
            print("world")
        j*=2
    i*=2

案例i==j外循环的每次迭代(i 发生变化)恰好发生一次，并且可以独立于 j 的值，并在 上从循环中取出j:

i=1
while i<=n
    j=1
    while j<=n
        if i!=j
            print("world")
        j*=2
    k=1
    while k<=i
        k+=1
        print("hello")
    i*=2

这改变了 print 的顺序输出，但这与确定时间复杂度无关。我们甚至可以进一步拆分:

i=1
while i<=n
    j=1
    while j<=n
        if i!=j
            print("world")
        j*=2
    i*=2

i=1
while i<=n
    k=1
    while k<=i
        print("hello")
        k+=1
    i*=2

现在对于第一个外层循环的一次迭代，它的内层 while 循环迭代了 logn 次。该内部循环的每次迭代都需要常数时间。在一种情况下(当 i 等于 j 时)，减少工作量的时间是恒定的，因此我们的时间复杂度为 O(logn)-O (1) = O(logn) 对于这个 while循环。

第一个外层循环的时间复杂度为:

O(logn) * O(logn) = O((logn)²)

对于第二个外层循环的一次迭代，它的内部 while 循环迭代了 i 次，因此我们得到的迭代总数(当 n 是 2 的幂时)为 1 + 2 + 4 + 8 + ... + n，这是一个 binary expansion -- 等于 2(2^logn)-1 = 2n-1，时间复杂度为:

O(2n-1) = O(n)

对于整体的时间复杂度，我们取和，即

O((logn)²) + O(n) = O(n)。

插图

为了说明这个时间复杂度，请看一下这个实现，其中 n 在每次执行中都会增加，并且计算并返回工作单元。 n 与工作量的比值接近一个常数:

function work(n)  {
    var units = 0;
    var i=1
    while (i<=n) {
        var j=1
        while (j<=n) {
            if (i==j) {
                var k=1
                while (k<=j) {
                    k+=1
                    //print("hello")
                    units++;
                }
            } else {
                //print("world")
                units++;
            }
            j*=2
        }
        i*=2
    }
    return units;
}

// Demo
setTimeout(function loop(n=1) {
    var units = work(n);
    console.log(`n=${n}, work=${units}, ratio=${units/n}`);
    if (n < 100000000) setTimeout(loop.bind(null, n*2));
});

这只是一个例子，不能算作证据。