大多数拥有计算机科学学位的人肯定知道大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.

对于第一种情况,内部循环执行了n-i次,因此执行的总次数是i从0到n-1(因为小于,而不是小于或等于)的和。你得到最后n * (n + 1) / 2,所以O (n²/ 2)= O (n²)。

对于第二个循环,i在0到n之间。然后,当j严格大于n时执行内循环,这是不可能的。

我想从另一个角度来解释Big-O。

Big-O只是用来比较程序的复杂性,也就是当输入增加时它们的增长速度有多快,而不是花在执行操作上的确切时间。

恕我直言,在大o公式中,你最好不要使用更复杂的方程(你可以坚持使用下图中的方程)。然而,你仍然可以使用其他更精确的公式(如3^n, n^3,…),但有时会误导!所以还是尽量简单为好。

我想再次强调,这里我们不想得到一个精确的算法公式。我们只想展示当输入增加时它是如何增长的并在这方面与其他算法进行比较。否则,您最好使用不同的方法,如基准测试。

对于代码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)

经常被忽视的是算法的预期行为。它不会改变你的算法的大o,但它确实与“过早优化.. ..”的声明有关

你的算法的预期行为是——非常简单——你期望你的算法在你最有可能看到的数据上工作的速度有多快。

例如,如果你在一个列表中搜索一个值,它是O(n),但如果你知道你看到的大多数列表都有你的值在前面,你的算法的典型行为会更快。

为了真正确定它,你需要能够描述你的“输入空间”的概率分布(如果你需要对一个列表排序,这个列表已经被排序的频率是多少?有多少次是完全相反的?多长时间进行一次排序?)这并不总是可行的,但有时你知道。