为什么算法渐进复杂度中对数的底数总为2
浏览:2497次 出处信息
在分析各种算法时,经常看到
三分式归并排序的时间复杂度
先看一个小例子。
大多数人应该对归并排序(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天十大热文
- [11] 解决 ubuntu 的 /etc/hosts
- [10] 文言文白话文互转:文言文转白话文(现代文),
- [9] 一个 VLA (可变长度数组)的实现
- [9] 用邻接表实现无向图
- [9] Http/2知识图谱
- [8] arduino-蓝牙各种版本类型及费用对比
- [8] 领导需要比下属更懂技术吗?
- [7] 近场通信 vs. 低功耗蓝牙:如何抉择
- [7] 为什么数组标号是从0开始的?
- [7] JVM内存结构