1

我有两段单独的代码，我需要计算它们的 Big O 复杂度。第一个是：

k:=1;
s := 4;
while k < N do
begin
    k := 2 * k;
    m:=1;
    while m < N do
    begin
       for i := m to 2*m-1 do s := s + 2;
       m := m + m;
    end;
end;

正确答案是 N*log(N)。第二段代码是：

m:=1;
FOR i:=n downto 1 do
BEGIN
  m:=m*2;
  y:=i MOD 2;
  x:=m;
  WHILE x>y DO
  BEGIN
     x:=x DIV 2;
     y:=y*2
 END    
END

第二个的正确答案是 n*n。我似乎无法正确计算我的数学。如果你能帮助任何一个，那将是很大的帮助。

4

1 回答 1

0

让我们看一下第一段代码：

k := 1;
s := 4;
while k < N do
begin
    k := 2 * k;
    m := 1;
    while m < N do
    begin
       for i := m to 2*m-1 do s := s + 2;
       m := m + m;
    end;
end;

需要注意的一点是，内循环和外循环是完全相互独立的，所以我们可以分别进行分析。让我们从内部循环开始。

当这个循环运行时，取值m将是 1、2、4、8、16、32 等，因为在每次迭代中 m 都加倍。在循环内部，还有第三个较小的循环，总共运行了 m 次。这意味着如果外部循环运行 k 次，则循环的总运行时间将由下式给出

1 + 2 + 4 + 8 + ... + 2 k

需要注意的一件事是，一旦m≥ ，内部循环就会终止N。由于在迭代k中 的值为m2 k，因此一旦 2 k ≥ ，循环就会停止运行N。只要 k 至少为 log 2 N，就会发生这种情况。因此，循环最多运行 log 2 N 次，所以这里完成的总工作是

1 + 2 + 4 + 8 + ... + 2 lg N = 2 lg N + 1 - 1 = 2N - 1

在这里，我使用几何级数之和的公式来简化总和。这意味着循环体的每次迭代都会做 Θ(N) 的工作。

现在剩下要做的就是弄清楚外循环要运行多少次。请注意，与内循环一样，外循环由一个在每次迭代时加倍的变量（即k）控制。使用类似的逻辑，我们得到这个循环将运行 Θ(log N) 次，因此总运行时间将为 Θ(N log N)。

一些要点：

有用的提示 #1：由变量控制的循环在每次迭代时大小翻倍，并在变量达到某个限制时停止 N 将运行 O(log N) 次。

有用的提示 #2： 1 + 2 + 4 + ... + 2 k = 2 k+1 - 1

现在，让我们看第二段代码：

m := 1;
FOR i := n downto 1 do
BEGIN
  m := m * 2;
  y := i MOD 2;
  x := m;
  WHILE x > y DO
  BEGIN
     x := x DIV 2;
     y := y*2
 END    
END

和以前一样，请注意变量m在每次迭代时都会加倍。这可能会很有趣，因为 m 的值将是 1、2、4、8、16、32、64 等。更一般地说，在迭代i时，m其值为 2 i。

现在，让我们看看内部循环会做多少工作。请注意，它x从 的值开始m，即 2 i。在循环的每次迭代中，x 减少两倍。这意味着此循环的最大可能迭代次数为 log m = log 2 i = i。这当然很好，因为这意味着内部循环总是在大多数i时候运行！

一旦我们有了它，确定运行时就不是很难了。由于 i 从 N 倒数到 0，所以完成的总功最多为

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

因此运行时间为 O(n 2 )。

希望这可以帮助！

于 2013-10-27T00:13:46.707 回答