为什么算法渐进复杂度中对数的底数总为2
浏览:2509次 出处信息
在分析各种算法时,经常看到
三分式归并排序的时间复杂度
先看一个小例子。
大多数人应该对归并排序(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天十大热文
- [258] 招聘技巧一二
- [13] 个人开公司的流程,以后用得着
- [13] 我对技术方向的一些反思
- [13] linux内核研究笔记(一)内存管理 – p
- [13] Linux常用系统信息查看命令
- [11] Redis和Memcached的区别
- [11] ps - 按进程消耗内存多少排序
- [10] 我的程序员之路
- [10] DBA最缺的不是技术
- [10] Nginx+FastCgi+Php 的工作机