-1

What would be the efficieny of the following program, it is a for loop which runs for a finite no. of times.

for(int i = 0; i < 10; i++ )
{
   //do something here, no more loops though.
}

So, what should be the efficiecy. O(1) or O(n) ?

4

4 回答 4

9

这完全取决于for循环中的内容。此外，计算复杂度通常是根据输入的大小来衡量的，n在您的示例中，我看不到任何直接或间接地对输入的大小进行建模、表示或编码的内容。只有常数10。

此外，虽然有时对计算复杂度的分析可能会给出意想不到的、令人惊讶的结果，但正确的术语不是“ Big Oh ”，而是Big-O。

于 2013-05-17T10:25:39.773 回答
4

您只能谈论与计算的某些特定输入有关的复杂性。如果您循环十次，因为您需要为十个“事物”工作，那么您的复杂性对于这些事物是 O(N)。如果您只需要循环 10 次而不考虑事物的数量 - 并且循环内的处理时间不会随着事物的数量而变化 - 那么您对它们的复杂性是 O(1)。如果没有“某物”的顺序大于 1，那么将循环描述为 O(1) 是公平的。

有点进一步漫无边际的讨论......

O(N) 表示完成工作所花费的时间可以合理地近似为某个恒定的时间量加上 N 的某个函数 - 输入中某些东西的数量 - 对于 N 的巨大值：

  • O(N) 表示时间为 c + xN，其中 c 是固定开销，x 是每个事物的处理时间，
  • O(log 2 N) 表示时间为 c + x(log 2 N)，
  • O(N 2 ) 表示时间为 c + x(N 2 )，
  • O(N!) 表示时间是 c + x(N!)
  • O(N N ) 表示时间为 c + x(N N )
  • ETC..

同样，在您的示例中没有提及输入的数量，并且循环迭代是固定的。我可以看到即使有 10 个输入“东西”，说它是 O(1) 是多么诱人，但请考虑：如果你有一个能够处理任意数量输入的函数，那么决定你只会在你的具有恰好 10 个输入和硬代码的应用程序，您显然没有改变函数的性能特征 - 您只是锁定在 time-for-N-input 曲线上的一个点 - 以及任何大 O 复杂性在硬编码之前有效的内容必须在之后仍然有效。尽管 N of 10 是一个很小的数量，但它的意义和用处不大，除非你有一个可怕的大 O 复杂性，比如 O(N N) 常数 c 和 x 在描述整体性能方面比它们对于 N 的巨大值更重要（其中 big-O 符号的变化通常比改变 c 甚至 x 对性能的影响要大得多 - 这是当然是进行大 O 分析的重点）。

于 2013-05-17T10:32:20.697 回答
2

当然是 O(1)，因为这里没有什么不与 n 线性相关。

编辑： 让循环体包含一些复杂的动作，在大 O 术语中复杂度为 O(P(n))。

如果我们有恒定的 C 次迭代，则循环的复杂度将为 O(C * P(n)) = O(P(n))。

否则，现在让迭代次数为 Q(n)，取决于 n。它使循环的复杂度为 O(Q(n) * P(n))。

我只是想说，当迭代次数恒定时，它不会改变整个循环的复杂性。

于 2013-05-17T10:26:21.197 回答
1

n用大 O 表示法表示输入大小。我们无法判断复杂性是什么，因为我们不知道for循环内部发生了什么。例如，可能有递归调用，取决于输入大小？在这个例子中，总体是O(n)：

void f(int n) // input size = n
{
    for (int i = 0; i < 10; i++ )
    {
        //do something here, no more loops though.
        g(n); // O(n)
    }
}

void g(int n)
{
    if (n > 0)
    {
        g(n - 1);
    }
}
于 2013-05-17T10:28:08.603 回答