小弟最近学算法 关于比较排序算法的一个小问题。。。
证明 为什么 排序算法 运行复杂度 至少 NlogN.....老师讲了半天 我是一点没懂
他说 假设 有一组数 a1 a2 a3 ... an 可能的排序 有 n！ 种
对于所有n排序的可能性 设置k 为最大的比较次数
则有 2的k次方 <= n!
最后得 n <= n/2(Log n/2) <= N log N.....完全没懂 --------------------编程问答-------------------- http://blog.csdn.net/wolf_y/article/details/8749950 --------------------编程问答-------------------- LS 看清在回答 --------------------编程问答-------------------- http://zhidao.baidu.com/question/48344061.html --------------------编程问答-------------------- 这是数学问题， --------------------编程问答--------------------
这个就好像是你们老师“自言自语”。
假设所所谓的算法最好情况是只能“一分为二”地进行递归处理，比如说有1万个数要排序，先分为5000个数的两组数据，保证前一组数据中每一个数都不大于后一组数据中的每一个数，然后这就可以分别在两个数据组上递归排序。
此时时间复杂度函数是 T(k) = P(k)+T(k/2)+T(k/2)，这里P(n)表示k个元素上“一分为二”所需要花费的时间。由于它是线性的（与n的规模同比增大的），实际上类似于 a*k + b，其中a和b都是常量。
那么你就能列出
T(k)=P(k)+2(T(k/2)
T(k/2)=P(k/2)+2T(k/4)
T(k/4)=P(k/4)+2T(k/8)
........
T(1)=1
把上面的左右想加，消去左右重复像，你就知道T(k)其实是 a*(k + k/2 + k/4 + .....1) + 一个常量
有 log2(k) 个数相加，并且后一个数十前一个数的一半。通过一个数学上叫做“等比数列求和公式”的东西，可以知道上面的求和结果。
当考察k变化时求和公式的变化速率，就是对k求导数，可以看到常量可以消去，最终这个计算时间的变化速率是：当k增大时，时间公式也以 n*log2(n) 级别增大。
理解这个，必须想象一下基本算法，然后才能递推。
至于你们老师那种匪夷所思的前后关系，太能凑数了，确实难以理解。 --------------------编程问答-------------------- 嗯，上面的求和是不对的，结果是 a*k + 2a*k + 4a*k ......
总共有 log2(k) 各项想加
这个等比数列 --------------------编程问答-------------------- 除
补充：.NET技术 , C#
