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

发布网友发布时间：2022-04-29 23:39

共3个回答

热心网友时间：2023-10-10 13:17

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

热心网友时间：2023-10-10 13:18

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

热心网友时间：2023-10-10 13:18

组的手向那边窜

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

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