你如何看待O(log n)和O(n log n)之间的差异？

Question

二进制搜索有一个平均情况下的性能,O(log n)并快速排序用O(n log n)的O(n log n)是同为O(n)+ O(log n)的

Answer 1

想象一下与世界上每个人的数据库.这是67亿条目.O(log n)是对索引列(例如主键)的查找.O(n log n)在未索引的列上按排序顺序返回整个总体.

• O(log n)在你读完那句话的第一个单词之前就完成了.
• O(n log n)仍在计算......

想象它的另一种方式:

log n 与n中的位数成比例.

n log n 是n倍.

尝试写1000一次这个数字而不是写一千次.第一个占用O(log n)时间,第二个占用O(n log n)时间.

现在再试一次6700000000.写一次仍然是微不足道的.现在尝试写入67亿次.即使你每秒钟写一次,你也会在你完成之前死去.

Answer 2

你可以想象它在一个情节,看到这里,例如: