2 u010949779 u010949779 于 2013.09.14 20:20 提问

快速排序的时间复杂度O(nlogn)

谁可以解释下O(nlogn) 是什么意思吗。。我知道n是需要循环的次数。logn呢。?

2个回答

phoenixylf
phoenixylf   2013.09.16 10:25
已采纳

logn是指用到了二分查找。即每次取之前总数的一半。直到最后一个就是我们要找的。
数学解释:假设原来总的个数为N个,每次查找为上一次的一半,经过x次找到我们要的结果。
公式表达:N*(1/2)^x=1;(x为指数)
解:x=log2(N)=logN(简写);
数学的计算相信你没问题的。

tlxzsz
tlxzsz   2014.02.27 17:44

logn是数学运算符,表示以2为底n的对数。
logn是指用到了二分查找。即每次取之前总数的一半。直到最后一个就是我们要找的。
数学解释:假设原来总的个数为N个,每次查找为上一次的一半,经过x次找到我们要的结果。
公式表达:N*(1/2)^x=1;(x为指数)
解:x=log2(N)=logN(简写);
数学的计算相信你没问题的。

Csdn user default icon
上传中...
上传图片
插入图片