代码的复杂性

Question

只有一个循环的程序的复杂性是什么，是log n吗？有人可以给我一些关于估算代码复杂性的想法吗？

Answer 1

那么，这实际上取决于该循环中发生的事情。

该循环是线性时间，即O（n）：

int sum = 0;
foreach( int i in SomeCollection )
{
    sum += i;
}

但是，请考虑在每次迭代期间执行子字符串搜索的循环。现在你必须考虑字符串搜索算法的复杂性。你的问题无法回答。如果您需要有意义的答案，则需要提供代码示例。

Answer 2

Software Complexity

有一个研究领域试图量化这一点。

它被称为cyclomatic complexity。

在这种情况下，我相信你的复杂性评级是p = 2，因为循环是有条件的，这意味着通过该方法有两条路径。

Time complexity

如果您指的是time complexity，它仍然只是O（1），除非循环迭代计数是通过多项式或指数函数导出的，可能是间接的，因为该方法本身是在更高的循环中调用，或者因为循环计数器实际上是乘以字符串操作或较低级别的操作。

Answer 3

要获得一段代码的Big-O复杂性，您需要问自己“完成了多少迭代”？

问题当然是，从代码本身中弄清楚并不总是那么容易，有时候最好还是看一下大局并计算完成的操作量。

例子：

For (i = 0 ; i < n ; i++ ) {
   //Do stuff
}

这是一个复杂性

For (i = n ; i > 0 ; i= i/2 ) {
   //Do stuff
}

这是一个复杂性......因为在每次迭代中我被减半。

void Mess (int n) {
    for (i = 0 ; i < n ; i++) {
         //Do stuff
         Mess(n-1);
    } 
}

现在这看起来像一个简单的循环，因为它用递归调用自身，它实际上非常混乱....每次迭代用n-1调用自己n次。 所以在这里从头到尾想起来会更容易。如果n == 1，则进行1次迭代。如果n == 2则它会调用前一个场景两次。 因此，如果我们将调用该函数，我们可以看到我们将以递归方式得到这些内容：最终当然会给我们n！

最重要的是，它并不总是微不足道的。

Answer 4

如果只有一个循环，它可能是循环体执行的次数....但是当然你可能在库调用中有许多隐藏的循环。如果你在循环体内发生n，O(n^2)等，那么很容易制作一个循环来执行strlen次memcpy或更糟。

或者更糟糕的是，如果你有一个带有正则表达式的库（或语言）并且他们的正则表达式实现是天真的（比如Perl），那么用一个循环O(2^n)很容易制作一个程序！正确编写的正则表达式实现不会发生这种情况。

Answer 5

您可以使用诸如“trend-prof”（https://pdfs.semanticscholar.org/8616/7f320e230641299754e0fbd860c44f5895f0.pdf）之类的工具轻松预测代码的计算时间和复杂性。

出于R代码的相同目的，Github中提供了GuessCompx库。

Answer 6

如果你要问的是Big-O时间复杂度，那么对于循环它是n乘以循环内的任何复杂性，其中n是循环计数限制。

所以。如果循环内的代码占用恒定时间，即如果其时间复杂度为O（1），则循环的复杂度将为O（1 * n）= O（n）。

以类似的方式，如果在循环内你有另一个循环，它将使m步骤，那么你的整个代码是O（n * m），依此类推。