algorithm - O(n log n) vs O(n)——时间复杂度的实际差异

Question

n log n > n -- 但这就像一个伪线性关系。如果n=10亿，记录n~30；

因此 n log n 将为 300 亿，即 30 X n，n 的阶数。我想知道 n log n 和 n 之间的时间复杂度差异在现实生活中是否很重要。

例如:使用快速选择算法在未排序数组中查找第 k 个元素的快速选择是O(n)。

如果我对数组进行排序并找到第 k 个元素，它是 O(n log n)。要对包含 1 万亿 元素的数组进行排序，如果我执行 quicksort 和索引，我将60 倍 慢.

Answer 1

Big-O 表示法的主要目的是让您像您在博文中所做的那样进行估算，并自行决定是否值得花费额外的 CPU 周期来编写通常更高级的算法将购买该代码改进。根据具体情况，您可能会得到不同的答案，即使您的数据集相对较小:

• 如果您在移动设备上运行，并且算法占执行时间的很大一部分，那么减少 CPU 使用会转化为延长电池生命周期
• 如果您在一个全有或全无的竞争环境中运行，例如高频交易系统，微观优化可能会区分赚钱和亏钱
• 当您的分析显示所讨论的算法在服务器环境中支配执行时间时，切换到更快的算法可能会提高所有客户端的性能。

Big-O 表示法隐藏的另一件事是常量乘法因子。例如，Quick Select 具有非常合理的乘数，因此在极大的数据集上使用它所节省的时间非常值得实现它的麻烦。

您需要记住的另一件事是空间复杂度。通常，具有 O(N*Log N) 时间复杂度的算法具有 O(Log N) 空间复杂度。对于非常大的数据集，这可能会带来问题，例如，当递归函数在堆栈容量有限的系统上运行时。