0

begin

          Input: n (pos. Integer)
          Output: y (pos. Integer)
          Other: x, z (pos. Integer)
                y := 0;
                x :=0;

                while x < n do
                      y := y + 1;
                      z := 0;
                      while z < 4 do
                          x := x + 1;
                          z := z + 1;
                      end;
                      for (i=0;i<2;i++){ 
                          x=x-1;
                      }
                End;

How is this done? I know that when there is a for loop it's O(N) and when there is a while it's O(log N) . I would appreciate the help :)

Thank you

4

1 回答 1

0

一个很好的方法是确定外循环执行了多少次以及每次迭代做了多少工作。

循环体如下：

            y := y + 1;
            z := 0;
            while z < 4 do
                  x := x + 1;
                  z := z + 1;
            end;
            for (i=0;i<2;i++){ 
                     x=x-1;
            }

第一行确实 O(1) 工作，第二行也是如此。逻辑的下一部分是一个运行四次的循环，每次迭代执行 O(1) 工作。因此，这个内部循环也确实 O(1) 工作。最后，剩余的循环完成 O(1) 的工作。因此，循环的每次迭代都会做 O(1) 的工作。

那么外循环执行了多少次呢？嗯，循环是

while x < n do

x 从零开始，请注意，在每次迭代中，循环将 x 递增四次，并将 x 递减两次。因此，在循环的每次迭代中，x 都会增加 2。因此，循环迭代的次数大致为 n / 2 = O(n)。

由于循环运行 O(n) 次并且每次迭代做 O(1) 工作，所以这里完成的总工作是 O(n)。

希望这可以帮助！

于 2013-05-22T19:09:46.637 回答