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

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


当前回答

基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。

很少(除非你正在编写一个具有广泛基库的平台(例如,.NET BCL或c++的STL),你会遇到比查看循环(for语句,while, goto等…)更困难的事情。

其他回答

将算法分解成你知道的大O符号,并通过大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²)一样,没有格式。

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

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

对于代码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时间是有用的,但了解一些一般情况可以在很大程度上帮助您在算法中做出决策。

以下是一些最常见的案例,摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) -确定一个数字是偶数还是奇数;使用常量大小的查找表或哈希表

O(logn) -用二分搜索在排序数组中查找一个项

O(n) -在未排序的列表中查找一个项;两个n位数相加

O(n2) -用一个简单的算法乘以两个n位数字;添加两个n×n矩阵;冒泡排序或插入排序

O(n3) -用简单的算法乘以两个n×n矩阵

O(cn) -使用动态规划找到旅行商问题的(精确)解;使用蛮力判断两个逻辑语句是否等效

O(n!) -通过暴力搜索解决旅行推销员问题

O(nn) -通常用来代替O(n!)来推导更简单的渐近复杂度公式