为O（n log n）的VS为O（n） - 在时间复杂度的实际差异 [英] O(n log n) vs O(n) -- practical differences in time complexity
问题描述
N日志N'GT; ñ - 但是这就像一个伪线性的关系。如果 N = 1十亿，日志N〜30;
n log n > n -- but this is like a pseudo-linear relationship. If n=1 billion, log n ~ 30;
让 N日志ñ将 30十亿，这是 30×N个，以便这个时间复杂度差的n log n和n 是在现实生活中显著。
so n log n will be 30 billion, which is 30 X n, order of n.
I am wondering if this time complexity difference between n log n and n are significant in real life.
例如：a 快速选择上找到在排序的数组的第k个元素是quickselect O（N）算法
Eg: A quick select on finding kth element in an unsorted array is O(n) using quickselect algorithm.
如果我对数组进行排序，找到第k个元素，它是为O（n log n）的。要排序与 1万亿元素的数组，我将 60倍慢，如果我做的快速排序和指数它。对我来说，这听起来像没有很大的区别，但我需要在这里专家的意见。
if I sort the array and find the kth element, it is O(n log n). To a sort an array with 1 trillion elements, I will be 60 times slower if I do quicksort and index it. To me it sounds like not a big difference, but I need opinion of experts here.
推荐答案
大O表示法的主要目的是让你去做那些你在您的文章做了估计，并决定为自己，如果花费你的努力编码一个典型的更先进的算法是值得的额外的CPU周期，你要购买与code改进。根据不同的情况下，你可能会得到不同的答案，即使你的数据集是比较小的：
The main purpose of the Big-O notation is to let you do the estimates like the ones you did in your post, and decide for yourself if spending your effort coding a typically more advanced algorithm is worth the additional CPU cycles that you are going to buy with that code improvement. Depending on the circumstances, you may get a different answer, even when your data set is relatively small:
- 如果您在移动设备上运行，并且该算法重新presents的执行时间显著部分，削减CPU的使用转化为延长电池的使用寿命
- 如果您正在运行在一个全有或全无的竞争环境中，比如高频交易系统，一个微型的优化可以赚钱和赔钱区分
- 当你的分析表明，该算法有问题占主导地位的执行时间在服务器环境中，切换到更快的算法可以改善您的所有客户端的性能。
另一件事的大O符号隐藏的是不断的倍增系数。例如，快速选择具有非常合理的倍数，从使用它非常大的数据集，非常值得推行它的麻烦，使节约时间。
Another thing the Big-O notation hides is the constant multiplication factor. For example, Quick Select has very reasonable multiplier, making the time savings from employing it on extremely large data sets well worth the trouble of implementing it.
这是你需要记住的另一件事是空间的复杂性。很多时候，算法与 O（N * log n）的时间复杂度将有一个 O（log n）的空间复杂度。这可能present一个问题非常大的数据集，例如，当一个递归函数具有有限堆容量的系统上运行。
Another thing that you need to keep in mind is the space complexity. Very often, algorithms with O(N*Log N) time complexity would have an O(Log N) space complexity. This may present a problem for extremely large data sets, for example when a recursive function runs on a system with a limited stack capacity.
这篇关于为O（n log n）的VS为O（n） - 在时间复杂度的实际差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
