比较大O表示法 [英] Compare Big O Notation

问题描述

在n元素数组中进行排序处理；
在X算法中:10 ^-8 n ² 秒，
在Y算法10 ^-6 n log ₂ n sec，
在Z算法10 ^-5 秒中.

In n-element array sorting processing takes;
in X algorithm: 10^-8n² sec,
in Y algoritm 10^-6n log₂n sec,
in Z algoritm 10^-5 sec.

我的问题是我该如何比较它们.例如，对于y，根据x可以更快地工作，我应该选择哪个元素数量?

My question is how do i compare them. For example for y works faster according to x, Which should I choose the number of elements ?

推荐答案

比较Big-Oh表示法时，您将忽略所有常量:

When comparing Big-Oh notations, you ignore all constants:

N ^ 2具有比N * log(N)更高的增长率，后者仍比O(1)[恒定]更快.

N^2 has a higher growth rate than N*log(N) which still grows more quickly than O(1) [constant].

N的幂决定增长率.

The power of N determines the growth rate.

示例:

O(n^3 + 2n + 10) > O(200n^2 + 1000n + 5000)

忽略常量(您应该进行纯大欧姆比较)，这可以简化为:

Ignoring the constants (as you should for pure big-Oh comparison) this reduces to:

O(n^3 + n) > O(n^2 + n)

进一步降低而忽略低阶术语，则得出结果:

Further reduction ignoring lower order terms yields:

O(n^3) > O(n^2)

因为N 3 > 2的幂.

Big-Oh遵循这样的层次结构:

Big-Oh follows a hierarchy that goes something like this:

O(1) < O(log[n]) < O(n) < O(n*log[n]) < O(n^x) < O(x^n) < O(n!)

(其中x大于1的任何量，甚至最小的位.)

(Where x is any amount greater than 1, even the tiniest bit.)

您可以通过一些规则来比较其他任何以n表示的表达式，这些规则我不会在此处发布，但是应该在Wikipedia中进行查找.我列出O(n*log[n])是因为它在排序算法中很常见.有关具有不同底数或不同幂的对数的详细信息，请查看参考源(我是否提到了Wikipedia?)

You can compare any other expression in terms of n via some rules which I will not post here, but should be looked up in Wikipedia. I list O(n*log[n]) because it is rather common in sorting algorithms; for details regarding logarithms with different bases or different powers, check a reference source (did I mention Wikipedia?)

试一下Wiki文章: http://en.wikipedia.org/wiki/Big_O_notation

Give the wiki article a shot: http://en.wikipedia.org/wiki/Big_O_notation

这篇关于比较大O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！