为什么算法渐进复杂度中对数的底数总为2
浏览:2510次 出处信息
在分析各种算法时,经常看到
三分式归并排序的时间复杂度
先看一个小例子。
大多数人应该对归并排序(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天十大热文
- [59] Go Reflect 性能
- [18] [译]Google Chrome中的高性能网
- [16] 关于Linux的文件系统cache
- [16] 在FreeNAS/BSD搭建基于Nginx+
- [14] 最近总结的一些技巧(vim,python,s
- [13] Linux常用系统信息查看命令
- [11] PHP加速器 eaccelerator 缓存
- [9] 精于图片处理的10款jQuery插件
- [9] base64_encode 和 urlenc
- [9] Linux(Ubuntu 10.04)上安装