Clo*_*oak 0 algorithm big-o asymptotic-complexity
在n元素数组中进行排序处理;
在X算法中:10 -8 n 2秒,
在Y算法中10 -6 n log 2 n sec,
在Z algoritm 10 -5 sec.
我的问题是如何比较它们.例如,根据x,y的工作速度更快,我应该选择哪些元素？
比较Big-Oh表示法时,忽略所有常量:
N ^ 2具有比N*log(N)更高的生长速率,其仍然比O(1)[常数]更快地生长.
N的力量决定了增长率.
例:
O(n^3 + 2n + 10) > O(200n^2 + 1000n + 5000)
忽略常量(正如你应该为纯粹的大哦比较),这减少到:
O(n^3 + n) > O(n^2 + n)
进一步减少忽略低阶条款产生:
O(n^3) > O(n^2)
因为N的力量3 > 2.
Big-Oh遵循以下类似的层次结构:
O(1) < O(log[n]) < O(n) < O(n*log[n]) < O(n^x) < O(x^n) < O(n!)
(其中x是大于1的任何数量,即使是最小的数量.)
你可以通过一些我不会在这里发布的规则来比较任何其他表达式,但是应该在维基百科中查找.我列出O(n*log[n])是因为它在排序算法中很常见; 有关不同基数或不同权力的对数的详细信息,请查看参考源(我是否提到过维基百科？)
给wiki文章一个镜头:http://en.wikipedia.org/wiki/Big_O_notation