-1

Fizz-Buzz 函数（在伪代码中）采用任何正整数n。我特别好奇 if-else 语句所需的成本和时间的代数分解。我知道它最坏的情况下运行时间是 O(n)。

Fizz-Bizz(n)
  for i = 1 to n
    if (n % 3 == 0)
      print "fizz"
    if (n % 5 == 0)
      print "buzz"
    if (n % 3 != 0 and n % 5 != 0)
      print n

另一种算法的分解示例：在此处输入图像描述

4

1 回答 1

2

时间复杂度是O(n)因为该if语句对此没有实际影响。if在足够大的数据集上，语句的复杂性是恒定的。

该语句实际上可能在迭代中执行不同数量的工作，其中您有 3 或 5 的倍数，但是每次循环迭代if的额外工作量不依赖于. 事实上，它随着变大而平均为一个常数。nn

而且，顺便说一句，我认为该代码可能是错误的。在 15 的倍数时，它应该同时打印fizz 和 buzz。

如果您想在编辑中做到这一点（添加的细分），您只需为每个语句分配一个任意成本（并且该成本对于该语句的单次执行是恒定的）然后计算每个语句的次数语句运行。ci

例如，第一个if序列运行n次数，print "fizz"其中三分之一的运行次数，n/3. 所以你最终会得到这样的表：

                           cost   times
Fizz-Buzz(n)
  for i = 1 to n           c1     n
    if (n % 3 == 0)        c2     n
      print "fizz"         c3     n / 3       [call this a]
    else
      if (n % 5 == 0)      c4     n - a
        print "buzz"       c5     (n - a) / 5 [call this b]
      else
        print n            c6     n - a - b

根据您的示例将所有这些加起来（用n- 方程代替aand b），最后，您仍然会得到依赖于 的东西n，因此是一种O(n)算法。它看起来像：

  c1*n + c2*n + c3*n/3   + c4*(n-a)   + c5*(n-a)/5     + c6*(n-a-b)
= c1*n + c2*n + (c3/3)*n + c4*(n-n/3) + (c5/5)*(n-n/3) + c6*(n-n/3-(n-n/3)/5)
= c1*n + c2*n + (c3/3)*n + c4*(2/3)*n + (c5/5)*(2/3)*n + c6*(n-n/3-(n-n/3)/5)
= c1*n + c2*n + (c3/3)*n + (c4*2/3)*n + (c5*2/15)*n    + c6*(n*8/15)
= c1*n + c2*n + (c3/3)*n + (c4*2/3)*n + (c5*2/15)*n    + (c6*8/15)*n

   /             1         2             2                8    \
= ( c1  + c2   + - c3    + - c4       + -- c5          + -- c6  ) * n
   \             3         3            15               15    /

括号内的所有这些值实际上都是常数（因为它们是常数的倍数）所以整个事情是n.

现在，如果你在上面的那些方程中发现一个小错误，我不会太惊讶——我已经好几年没做过这个级别的数学了，如果这是为了作业，然后您尝试逐字复制它:-)

但是您可能会发现的唯一错误是常数乘数本身的值。它仍然是某些描述的常数乘数，我保证。

于 2014-06-26T06:21:54.873 回答