1

有人给我这段代码，我想找到确切的复杂性，或者换句话说，找到一个公式，让特定的 n 知道如何计算 L。

L = 0;
for (i = 1; i<n; i++)
    for (j = 1; j<i; j++)
        for (k = j; k<n; k++)
            L++;

我的第一个想法是 (n^3 + n^2)/2，但这是错误的。

例如 n=5 L=20 ；n=10 升=240

感谢：D

编辑：这个问题来自算法基础，第 140 页或 pdf 中的幻灯片 161（这是免费书籍版本） http://www.freebookspot.es/Comments.aspx?Element_ID=76025

4

2 回答 2

2

这是数学，不是编程。

L 等于（S 是 big-sigma，总和）：

    n-1   i-1   n-1
   S     S     S    1
   i=1   j=1   k=j

   n-1 i-1
= S   S  (n - j)
  i=1 j=1

   n-1 i-1      n-1 i-1
= S   S  n  -  S   S  j
  i=1 j=1      i=1 j=1 

       n-1          n-1 
= n * S   (i-1) -  S   (i-1)i/2
      i=1          i=1

等等。您需要知道第一个n整数的n(n+1)/2和是 并且第一个n平方和是n(n+1)(2n+1)/6。你最终会得到一个三次方程n。

感谢 Barmaley 指出我不再是本科生的回答，我不必操纵公式来简化它们。Wolfram Alpha会为我做这件事 ;-)

答案是n(n-1)(n-2)/3。通常当这些事情很好地分解时，结果证明我可以在早期做出一个关键的洞察力（也许是几何的洞察力），以便在不写太多长表达式的情况下得出答案。这个结果看起来很可疑，就像刻在一个长方体中的金字塔的体积n，n-1，n-2。

于 2013-02-06T17:50:27.020 回答
2

首先：复杂性与 n 的具体数量无关。这是关于渐近行为。当有人说算法的复杂度为 O(f(n)) 时，这并不意味着算法严格执行 f(n) 操作。事实上，它可以做2*f(n)or1/2 * f(n)或f(n) + sqrt(f(n))。在谈论复杂性时，人们通常对操作数量随着输入的增长而增长的速度感兴趣。

在您的情况下，您必须编写 3 个嵌套总和（每个循环一个）和内部操作的总和成本（假设它是 1）：

过程

这是精确的公式（不要相信我 - 检查使用wolfram|alpha），但在复杂性语言中它只是 O(n^3)

UPD：请注意，此公式对应于具有条件类型的循环，less-or-equal而不仅仅是less-than.

于 2013-02-06T17:58:44.567 回答