大多数拥有计算机科学学位的人肯定知道大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²)一样,没有格式。
其他回答
我从信息的角度来考虑。任何问题都包括学习一定数量的比特。
你的基本工具是决策点及其熵的概念。一个决策点的熵是它会给你的平均信息。例如,如果一个程序包含一个有两个分支的决策点,它的熵是每个分支的概率乘以该分支的逆概率的log2的和。这就是你从执行决策中学到的东西。
例如,一个if语句有两个分支,都是等可能的,其熵为1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1。所以它的熵是1比特。
假设您正在搜索一个包含N个条目的表,例如N=1024。这是一个10位问题,因为log(1024) = 10位。所以如果你可以用if语句搜索结果的可能性相等,它应该需要10个决定。
这就是二分搜索的结果。
假设你在做线性搜索。您查看第一个元素并询问它是否是您想要的元素。是的概率是1/1024,不是的概率是1023/1024。该决策的熵为1/1024*log(1024/1) + 1023/1024 *log(1024/1023) = 1/1024* 10 + 1023/1024 * about 0 =约0.01 bit。你学得太少了!第二个决定也好不到哪里去。这就是为什么线性搜索这么慢。事实上,你需要学习的比特数是指数级的。
假设你在做索引。假设表被预先排序到许多箱子中,并且您使用键中的所有位中的一些位直接索引到表项。如果有1024个箱子,熵为1/1024 * log(1024) + 1/1024 * log(1024) +…对于所有1024个可能的结果。这是1/1024 * 10乘以1024个结果,或者对一个索引操作来说是10比特的熵。这就是为什么索引搜索是快速的。
现在想想排序。你有N个项目,你有一个列表。对于每个项目,您必须搜索项目在列表中的位置,然后将其添加到列表中。排序大约需要N倍于底层搜索的步数。
基于二元决策的排序结果都是等概率的都需要O(N log N)步。基于索引搜索的O(N)排序算法是可行的。
我发现几乎所有的算法性能问题都可以用这种方式来看待。
我想从另一个角度来解释Big-O。
Big-O只是用来比较程序的复杂性,也就是当输入增加时它们的增长速度有多快,而不是花在执行操作上的确切时间。
恕我直言,在大o公式中,你最好不要使用更复杂的方程(你可以坚持使用下图中的方程)。然而,你仍然可以使用其他更精确的公式(如3^n, n^3,…),但有时会误导!所以还是尽量简单为好。
我想再次强调,这里我们不想得到一个精确的算法公式。我们只想展示当输入增加时它是如何增长的并在这方面与其他算法进行比较。否则,您最好使用不同的方法,如基准测试。
大O表示算法时间复杂度的上界。它通常与处理数据集(列表)一起使用,但也可以在其他地方使用。
下面是一些在C代码中如何使用它的例子。
假设我们有一个n个元素的数组
int array[n];
如果我们想要访问数组的第一个元素,这将是O(1)因为不管数组有多大,它总是需要相同的常数时间来获得第一项。
x = array[0];
如果我们想在列表中找到一个数字:
for(int i = 0; i < n; i++){
if(array[i] == numToFind){ return i; }
}
这是O(n)因为我们最多要遍历整个列表才能找到我们要的数。大O仍然是O(n),即使我们可能在第一次尝试中找到我们的数字并运行一次循环,因为大O描述了算法的上界(omega是下界,theta是紧界)。
当我们讲到嵌套循环时:
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
array[j] += 2;
}
}
这是O(n²)因为对于外层循环的每一次循环(O(n))我们都必须再次遍历整个列表,所以n乘以后只剩下n²。
这仅仅是触及表面,但当你分析更复杂的算法时,涉及证明的复杂数学就会发挥作用。希望这至少能让你熟悉基本知识。
我认为,一般来说用处不大,但为了完整起见,还有一个Big Omega Ω,它定义了算法复杂度的下界,还有一个Big Theta Θ,它同时定义了上界和下界。
我不知道如何通过编程来解决这个问题,但人们做的第一件事是我们对算法的特定模式进行抽样,比如4n²+ 2n + 1我们有两个规则:
如果我们有一个项的和,增长率最大的项被保留,其他项被省略。 如果我们有几个因数的乘积,常数因数就省略了。
如果我们化简f(x),其中f(x)是所做操作数量的公式,(上文解释的4n²+ 2n + 1),我们得到大O值[在这种情况下是O(n²)]。但这必须考虑到程序中的拉格朗日插值,这可能很难实现。如果真正的大O值是O(2^n)我们可能有O(x^n)这样的东西,那么这个算法可能是不可编程的。但如果有人证明我错了,给我代码. . . .