时间为O（nlg n）的排序算法 如快速排序 堆排序 nlg是什么意思。好象是lgn。 什么意思？

时间为O（nlg n）的排序算法 如快速排序 堆排序 nlg是什么意思。好象是lgn。 什么意思？

准确来说,是log(2,n),即以2为底取n的对数.
该时间复杂度的产生是由于算法中使用了二分法.二分法的其中一个显著的标志就是使得渐进复杂度变为2底对数级别.
直观来说,对于1000个数的排序,效率为O(n)的排序(假设有)将花费1000"单位"的时间,那么O(n²)的排序将花费10^6"单位"的时间.而O(nlogn)的排序将花费 1000*log(1000) ≈ 10000 "单位"的时间.
这里可以看出其效率的显著优势,
而通过函数有关特征可以得知,对数函数是增长的越来越慢的,这就使得O(nlogn)的排序可以在越大的工作量中和平方级排序拉大差距.

组的手向那边窜

lgn是对2取对数 意思是找一个数使得2^x=n那么lg n=x

你好！ lgn是对2取对数 意思是找一个数使得2^x=n那么lg n=x 仅代表个人观点，不喜勿喷，谢谢。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息