请选择 进入手机版 | 继续访问电脑版

技术控

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

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

[复制链接]
温柔被搁浅 发表于 2016-10-3 11:04:49
244 3

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n)),一般人认为,T(n)是f(n)中增长最快的项/此项的系数. 比方说

数学中的极限思想求时间复杂度

数学中的极限思想求时间复杂度-1-技术控-数学极限思想,极限思想
T(n) = 2n^5 + 3n^2 - 1 为

数学中的极限思想求时间复杂度

数学中的极限思想求时间复杂度-2-技术控-数学极限思想,极限思想
O(T(n) = O(2n^5/2) = O(n^5) 其实这是错误的计算方法, 真正意义上的时间复杂度而是数学中极限的概念.
  还是上面的例子,可以用下面的公式去转换:
   

数学中的极限思想求时间复杂度

数学中的极限思想求时间复杂度-3-技术控-数学极限思想,极限思想
\lim_{n\to\infty}\frac{T(n)} {\ xf(n)}= 常数 ( 其中x为项系数 )), 假如左边等式成立,则f(n)为T(n)的时间复杂度.什么意思呢?
  我们用上面的例子来看下:
   数学中的极限思想求时间复杂度-4-技术控-数学极限思想,极限思想 \lim_{n\to\infty}\frac{T(n)} {\ xf(n)}= lim_{n\to\infty}\frac{2n^5 + 3n^2 - 1}{\ 2n^5}   = 常数
   所以这个T(n)的时间复杂度为 数学中的极限思想求时间复杂度-5-技术控-数学极限思想,极限思想 O(n^5), 再举个通俗例子:
   比如求 数学中的极限思想求时间复杂度-6-技术控-数学极限思想,极限思想 n^k 和 数学中的极限思想求时间复杂度-7-技术控-数学极限思想,极限思想 k^n的时间复杂度的比较, 其中( k为常数,k>1,且k属于正整数 ), 如果按照之前的错误求法是很难求的, 试试极限的思想:
   数学中的极限思想求时间复杂度-8-技术控-数学极限思想,极限思想 \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
   因为 数学中的极限思想求时间复杂度-9-技术控-数学极限思想,极限思想 n\to\infty, 很简单的就可以通过极限求出来了,结果为: 数学中的极限思想求时间复杂度-10-技术控-数学极限思想,极限思想 O(n^k)要远远好于 数学中的极限思想求时间复杂度-11-技术控-数学极限思想,极限思想 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次,则:
   数学中的极限思想求时间复杂度-12-技术控-数学极限思想,极限思想 2^y*i = n 这里的i可以省略,不影响时间复杂度的计算, 所以 数学中的极限思想求时间复杂度-13-技术控-数学极限思想,极限思想 y = log_2n => 数学中的极限思想求时间复杂度-14-技术控-数学极限思想,极限思想 O(log_2n). 就说到这, 有问题请交流:)



上一篇:Electric Pair Mode In Emacs
下一篇:canvas在高倍屏下变模糊的处理办法
何振 发表于 2016-10-4 07:31:33
温柔被搁浅不整容也像雷锋!
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读


回页顶回复上一篇下一篇回列表
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )

© 2001-2017 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表