java代码的复杂性

Question

一个只有一个循环的程序的复杂度是多少，是logn吗？ 有人能给我一些关于估计代码复杂性的想法吗

Answer 1

要获得一段代码的大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 2

如果你问的是大O时间复杂度，那么对于循环来说，它是n倍于循环中任何东西的复杂度，其中n是循环计数限制

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

以类似的方式，如果在循环中有另一个循环将执行m步，那么整个代码就是O（n*m），以此类推

Answer 3

使用“趋势教授”（https://pdfs.semanticscholar.org/8616/7f320e230641299754e0fbd860c44f5895f0.pdf）等工具，您可以轻松预测代码的计算时间和复杂性

为了在R代码上实现同样的目的，Github中提供了GuessCompx库

Answer 4

软件复杂性

有一个研究领域试图准确地量化这一点

它叫cyclomatic complexity

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

时间复杂度

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

Answer 5

这真的取决于循环中发生了什么

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

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

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

Answer 6

如果只有一个循环，可能是循环体执行的次数。。。。当然，在库调用中可能有许多隐藏循环。很容易创建一个执行n次O(n^2)的循环，如果在循环体内部发生strlen、memcpy等情况，则更糟糕

甚至更糟糕的是，如果你有一个带有正则表达式的库（或语言），并且它们的正则表达式实现很简单（比如Perl），那么只需一个循环就可以很容易地生成一个程序O(2^n)！！如果使用正确编写的正则表达式实现，就不会发生这种情况