为什么算法渐进复杂度中对数的底数总为2
浏览:2513次 出处信息
在分析各种算法时,经常看到
三分式归并排序的时间复杂度
先看一个小例子。
大多数人应该对归并排序(merge sort)很熟悉,它的渐进复杂度为
递归分析
下面通过递归分析对三分式归并排序的时间复杂度进行分析。因为不管是三分还是二分,对于总共n个数据来说,一遍合并的复杂度为
如果把这个递归式的递归树画出来,很容易得到
对数的陷阱
那么这是否意味着三分式归并排序在时间复杂度上要优于二分式的归并排序呢?因为直觉上
实际上三分式归并排序的时间复杂度确实是
这看起来似乎是矛盾的,
其中a和c均大于0且不等于1。
更多内容详见原文:http://blog.codinglabs.org/articles/why-logarithm-base-of-asymptotic-time-complexity-always-two.html
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:内存异常排查
后一篇:开源压缩算法Zopfli介绍 >>
文章信息
- 作者:CodingLabs 来源: CodingLabs
- 标签: 渐进复杂度
- 发布时间:2013-03-03 23:10:09
近3天十大热文
- [16] 浏览器的工作原理:新式网络浏览器幕后揭秘
- [15] Go Reflect 性能
- [13] iOS下自己动手造无限循环图片轮播
- [13] 界面设计速成
- [13] iOS可视化编程 Tips 之“无需代码设置
- [13] Spark性能优化——和shuffle搏斗
- [12] iTerm2 (Mac Terminal)
- [12] iOS并发编程(Concurrency Pr
- [12] 最萌域名.cat背后的故事:加泰与西班牙政府
- [11] 内网穿透神器frp