algorithm - 比较大 O 表示法

Question

在 n 元素数组中排序处理需要；
在 X 算法中：10 ^-8 n ²秒，
在 Y 算法中 10 ^-6 n log ₂ n 秒，
在 Z 算法中 10 ^-5秒。

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

Answer 1

比较 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 的量，即使是最小的位。）

您可以通过一些我不会在此处发布但应该在 Wikipedia 中查找的规则来比较任何其他表达式。我列出O(n*log[n])是因为它在排序算法中相当常见；有关具有不同底数或不同幂的对数的详细信息，请查看参考来源（我提到过维基百科吗？）

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

Answer 2

我提出了这个不同的解决方案，因为还没有一个公认的答案。

如果您想查看n一种算法的性能比另一种更好，您应该将算法时间设置为彼此相等并求解n.

例如：

X = Z  
10^-8 n^2 = 10^-5  
n^2 = 10^3  
n = sqrt(10^3)
let c = sqrt(10^3)

所以比较Xand的时候Z，选择Xif nis less than c, Zif nis greater than c。这可以在其他两对之间重复。