大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。

但我很好奇,你是如何计算或近似你的算法的复杂性的?


当前回答

首先,公认的答案是试图解释漂亮的花哨的东西, 但我认为,故意让Big-Oh复杂化并不是解决办法, 这是程序员(或者至少是像我这样的人)寻找的。

Big Oh(简而言之)

function f(text) {
  var n = text.length;
  for (var i = 0; i < n; i++) {
    f(text.slice(0, n-1))
  }
  // ... other JS logic here, which we can ignore ...
}

上面的大写哦是f(n) = O(n!)其中n表示输入集中的条目数, f表示每一项所做的操作。


Big-Oh符号是算法复杂度的渐近上界。 在编程中:假设的最坏情况所花费的时间, 或假设逻辑的最大重复计数,为输入的大小。

计算

记住(从上面的意思);我们只需要受N(输入大小)影响的最坏情况时间和/或最大重复次数, 然后再看一下(公认答案的)例子:

for (i = 0; i < 2*n; i += 2) {  // line 123
    for (j=n; j > i; j--) {     // line 124
        foo();                  // line 125
    }
}

Begin with this search-pattern: Find first line that N caused repeat behavior, Or caused increase of logic executed, But constant or not, ignore anything before that line. Seems line hundred-twenty-three is what we are searching ;-) On first sight, line seems to have 2*n max-looping. But looking again, we see i += 2 (and that half is skipped). So, max repeat is simply n, write it down, like f(n) = O( n but don't close parenthesis yet. Repeat search till method's end, and find next line matching our search-pattern, here that's line 124 Which is tricky, because strange condition, and reverse looping. But after remembering that we just need to consider maximum repeat count (or worst-case time taken). It's as easy as saying "Reverse-Loop j starts with j=n, am I right? yes, n seems to be maximum possible repeat count", so: Add n to previous write down's end, but like "( n " instead of "+ n" (as this is inside previous loop), and close parenthesis only if we find something outside of previous loop.

搜索完成了!为什么?因为第125行(或之后的任何行)与我们的搜索模式不匹配。 现在我们可以关闭任何圆括号(在我们的记录中左开),结果如下:

f(n) = O( n( n ) )

试着进一步缩短“n(n)”部分,比如:

N (N) = N * N = n2 最后,用Big Oh符号来包装它,就像O(n2)或O(n²)一样,没有格式。

其他回答

看到这里的答案,我想我们可以得出这样的结论:我们大多数人确实通过观察它和使用常识来近似算法的顺序,而不是像我们在大学里认为的那样用主方法来计算它。 说了这么多,我必须补充一点,即使教授也鼓励我们(后来)实际思考,而不是仅仅计算。

我还想补充一下如何对递归函数进行处理:

假设我们有这样一个函数(scheme code):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

递归地计算给定数字的阶乘。

第一步是尝试并确定函数体的性能特征,只是在这种情况下,在函数体中没有做任何特殊的事情,只是一个乘法(或返回值1)。

所以主体的性能是:O(1)(常数)。

接下来尝试确定递归调用的数量。在这种情况下,我们有n-1个递归调用。

所以递归调用的性能是:O(n-1)(阶为n,因为我们抛弃了无关紧要的部分)。

然后把这两个放在一起,你就得到了整个递归函数的性能:

1 * (n-1) = O(n)


Peter, to answer your raised issues; the method I describe here actually handles this quite well. But keep in mind that this is still an approximation and not a full mathematically correct answer. The method described here is also one of the methods we were taught at university, and if I remember correctly was used for far more advanced algorithms than the factorial I used in this example. Of course it all depends on how well you can estimate the running time of the body of the function and the number of recursive calls, but that is just as true for the other methods.

我认为,一般来说用处不大,但为了完整起见,还有一个Big Omega Ω,它定义了算法复杂度的下界,还有一个Big Theta Θ,它同时定义了上界和下界。

对于代码A,外层循环将执行n+1次,“1”时间表示检查i是否仍然满足要求的过程。内循环运行n次,n-2次....因此,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)。

对于代码B,虽然内部循环不会介入并执行foo(),但内部循环将执行n次,这取决于外部循环的执行时间,即O(n)

首先,公认的答案是试图解释漂亮的花哨的东西, 但我认为,故意让Big-Oh复杂化并不是解决办法, 这是程序员(或者至少是像我这样的人)寻找的。

Big Oh(简而言之)

function f(text) {
  var n = text.length;
  for (var i = 0; i < n; i++) {
    f(text.slice(0, n-1))
  }
  // ... other JS logic here, which we can ignore ...
}

上面的大写哦是f(n) = O(n!)其中n表示输入集中的条目数, f表示每一项所做的操作。


Big-Oh符号是算法复杂度的渐近上界。 在编程中:假设的最坏情况所花费的时间, 或假设逻辑的最大重复计数,为输入的大小。

计算

记住(从上面的意思);我们只需要受N(输入大小)影响的最坏情况时间和/或最大重复次数, 然后再看一下(公认答案的)例子:

for (i = 0; i < 2*n; i += 2) {  // line 123
    for (j=n; j > i; j--) {     // line 124
        foo();                  // line 125
    }
}

Begin with this search-pattern: Find first line that N caused repeat behavior, Or caused increase of logic executed, But constant or not, ignore anything before that line. Seems line hundred-twenty-three is what we are searching ;-) On first sight, line seems to have 2*n max-looping. But looking again, we see i += 2 (and that half is skipped). So, max repeat is simply n, write it down, like f(n) = O( n but don't close parenthesis yet. Repeat search till method's end, and find next line matching our search-pattern, here that's line 124 Which is tricky, because strange condition, and reverse looping. But after remembering that we just need to consider maximum repeat count (or worst-case time taken). It's as easy as saying "Reverse-Loop j starts with j=n, am I right? yes, n seems to be maximum possible repeat count", so: Add n to previous write down's end, but like "( n " instead of "+ n" (as this is inside previous loop), and close parenthesis only if we find something outside of previous loop.

搜索完成了!为什么?因为第125行(或之后的任何行)与我们的搜索模式不匹配。 现在我们可以关闭任何圆括号(在我们的记录中左开),结果如下:

f(n) = O( n( n ) )

试着进一步缩短“n(n)”部分,比如:

N (N) = N * N = n2 最后,用Big Oh符号来包装它,就像O(n2)或O(n²)一样,没有格式。

如果你的成本是一个多项式,只保留最高次项,而不保留它的乘数。例如:

(O (n / 2) + 1) * (n / 2)) = O (n2/4 = O (n / 2) + n2/4) = O (n2)

注意,这对无穷级数不成立。对于一般情况,没有单一的方法,但对于一些常见情况,适用以下不等式:

O(log N) < O(N) < O(N log N) < O(N2) < O(Nk) < O(en) < O(n!)