数学中的极限思想求时间复杂度
一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n)),一般人认为,T(n)是f(n)中增长最快的项/此项的系数. 比方说T(n) = 2n^5 + 3n^2 - 1 为 O(T(n) = O(2n^5/2) = O(n^5) 其实这是错误的计算方法, 真正意义上的时间复杂度而是数学中极限的概念.
还是上面的例子,可以用下面的公式去转换:
\lim_{n\to\infty}\frac{T(n)} {\ xf(n)}= 常数 (其中x为项系数)), 假如左边等式成立,则f(n)为T(n)的时间复杂度.什么意思呢?
我们用上面的例子来看下:
\lim_{n\to\infty}\frac{T(n)} {\ xf(n)}= lim_{n\to\infty}\frac{2n^5 + 3n^2 - 1}{\ 2n^5} = 常数
所以这个T(n)的时间复杂度为O(n^5), 再举个通俗例子:
比如求 n^k 和k^n的时间复杂度的比较, 其中(k为常数,k>1,且k属于正整数), 如果按照之前的错误求法是很难求的, 试试极限的思想:
\lim_{n\to\infty}\frac{n^k} {\ k^n}=lim_{n\to\infty}\frac{log_2(n^k)}{\ log_2(k^n)} =lim_{n\to\infty}\frac{klog_2(n)}{\ nlog_2k} = 0
因为n\to\infty, 很简单的就可以通过极限求出来了,结果为: O(n^k)要远远好于O(k^n) .
顺便来说一下程序片段的时间复杂度,如下面的程序:
void fun (int n) { int i = 1; while (i <= n) { i = i*2; } }
上面这个程序可以看出 int i = 1;为O(1)的, 这里是求基本运算语句i = i*2 ,我们这里直接设它执行y次,则:
2^y*i = n 这里的i可以省略,不影响时间复杂度的计算, 所以y = log_2n => O(log_2n). 就说到这, 有问题请交流:)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:Crazybaby 来源: 狂Shell - Happy Hacking狂Shell - Happy Hacking
- 标签: 时间复杂度
- 发布时间:2013-04-07 13:14:34
- [66] Oracle MTS模式下 进程地址与会话信
- [65] Go Reflect 性能
- [64] 如何拿下简短的域名
- [60] android 开发入门
- [59] 图书馆的世界纪录
- [59] 【社会化设计】自我(self)部分――欢迎区
- [58] IOS安全–浅谈关于IOS加固的几种方法
- [54] 视觉调整-设计师 vs. 逻辑
- [48] 读书笔记-壹百度:百度十年千倍的29条法则
- [47] 界面设计速成