algorithm - 挑战大O

Question

我对 Big O 有疑问:

for i:=1 to n do
for j:=1 to i*i do 
begin
  k:=1; m:=n;
  while m>=k do 
  begin
    k:=k*3;
    m:=m/2
  end
end

老师给出了答案——n*n*n*log(n)。但是，我无法到达那里。这应该是基础 2 的对数。请帮忙。

Answer 1

在这里您可以看到零件的来源:

for i:=1 to n do      <-- n
for j:=1 to i*i do    <-- n*n
begin
  k:=1; m:=n;
  while m>=k do       <-- log(n)
  begin                    /
    k:=k*3;               /
    m:=m/2            <--+
  end
end

循环是嵌套的，所以你会增加它们的复杂性

为了理解 base 2 log，让我们从一个更简单的例子开始:

  while m>=k do
  begin
    k:=k*2;
    m:=m/2
  end

这个循环恰好运行 ⌈(log n)/2⌉ 次(以 2 为基数)，因为简单地说 m 和 k 在中间相遇(当然不是准确的中间!)在一半之后时间。常数因子 0.5 在 Big-O 中被忽略。对于 k:=k*3，情况类似，但结果将介于 (log n)/2(基数 3)和 (log n) 之间/2(基数 2)。我会把数学留给你，但你会明白 m:=m/2 更重要，因为它是从上到下开始的。