技术控

    今日:0| 主题:63445
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] 数学中的极限思想求时间复杂度

[复制链接]
温柔被搁浅 发表于 2016-10-3 11:04:49
286 3
一般情况下,算法的基本操作重复执行的次数是模块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) .
  顺便来说一下程序片段的时间复杂度,如下面的程序:
  1. void fun (int n) {
  2.     int i = 1;
  3.     while (i <= n) {
  4.         i = i*2;
  5.     }
  6. }
复制代码
上面这个程序可以看出 int i = 1;为O(1)的, 这里是求基本运算语句i = i*2 ,我们这里直接设它执行y次,则:
    2^y*i = n 这里的i可以省略,不影响时间复杂度的计算, 所以 y = log_2n => O(log_2n). 就说到这, 有问题请交流:)
何振 发表于 2016-10-4 07:31:33
温柔被搁浅不整容也像雷锋!
回复 支持 反对

使用道具 举报

脚本骆驼 发表于 2016-10-24 04:19:42
前排,坐等,支持温柔被搁浅,直播无敌,千秋万世
回复 支持 反对

使用道具 举报

玩偶的眼泪 发表于 2016-10-24 04:46:31
边撸边过
回复 支持 反对

使用道具 举报

我要投稿

推荐阅读


回页顶回复上一篇下一篇回列表
手机版/c.CoLaBug.com ( 粤ICP备05003221号 | 粤公网安备 44010402000842号 )

© 2001-2017 Comsenz Inc.

返回顶部 返回列表