运行嵌套循环的时间

Question

我确定这个嵌套循环的运行时间是 O(N*log(N))。运行内层循环的时间是log(N)，外层循环是N。

for (int i = 0; i < N; ++i) {
  for (int j = 1; j <= i; j *= 2) { 
  }
}

在内部循环中，如果我将 j *= 2 更改为 j *= 3 会怎样？在这种情况下，结果将如何变化？

Answer 1

它仍然是对数的。但是，它将按常数因子进行缩放（这与 Big O 分析无关）。

效果是对数的底发生变化（参见https://en.wikipedia.org/wiki/Logarithm#Change_of_base）。

Answer 2

---------[j = 2 * j] 对于 j < i:------------

j = 2*1 = 2 =>2^1
    2*2 = 4 =>2^2
    2*4 = 8 =>2^3
............. 2^k = n say n==i
if log applied on both side 2^k = n 
log(2^k) = logn
k = log_2(N) where 2 is the base

---------[j = 3 * j] 对于 j < i:------------

j = 3*1 = 3  =>3^1
    3*3 = 9  =>3^2
    3*9 = 27 =>2^3
.............loop stop when 3^k = n say n==i
if log applied on both side 3^k = n 
log(3^k) = logn
k = log_3(N) where 3 is the base

Answer 3

@Kevin 完全正确，但我想我会展示一些实验结果。您可以通过创建一个计数器来轻松地对此进行测试，该计数器在每个内部循环迭代中递增，并且运行用于不同的 N 值。然后可以采用 time = a * N * log(N) 的形式进行拟合。对于 j *= 2 的情况，我们得到一个系数 a = 1.28。对于 j *= 3，我们得到 a = 0.839。

我使用下面的 MATLAB 脚本生成了这张图：

clear
clc
close all

nmin = 10;
nmax = 1000;

count1 = zeros(nmax - nmin + 1, 1);

for n = nmin: nmax

    k = 0;
    for i = 0: n - 1
        j = 1;
        while (j <= i)
            j = j * 2;
            k = k + 1;
        end
    end

    count1(n - nmin + 1) = k;

end

ns = (nmin: nmax)';

figure
hold on
plot(ns, count1, '--')

a1 = mean(count1 ./ (ns .* log(ns)))

fit1 = a1 * ns .* log(ns);
plot(ns, fit1)

%%

count2 = zeros(nmax - nmin + 1, 1);

for n = nmin: nmax

    k = 0;
    for i = 0: n - 1
        j = 1;
        while (j <= i)
            j = j * 3;
            k = k + 1;
        end
    end

    count2(n - nmin + 1) = k;

end

ns = (nmin: nmax)';

plot(ns, count2, '-.')

a2 = mean(count2 ./ (ns .* log(ns)))

fit2 = a2 * ns .* log(ns);
plot(ns, fit2)

xlabel('N')
ylabel('Time complexity')
legend('j *= 2', 'j *= 2 fit', 'j *= 3', 'j *= 3 fit', 'Location', 'NorthWest')

Answer 4

如果您熟悉数学公式并且对更严格的精度感兴趣，您可以有条不紊地使用 Sigma 表示法，如下所示：

来自我的 blog：

运行嵌套循环的时间

Running Time of Nested Loops

algorithm

big-o

asymptotic-complexity

运行 嵌套循环的时间

Running Time of Nested Loops

algorithm

big-o

asymptotic-complexity

运行嵌套循环的时间