鱼C论坛

 找回密码
 立即注册
查看: 46|回复: 0

[学习笔记] 算法的时间复杂度

[复制链接]
最佳答案
17 
发表于 2018-10-11 23:02:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

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

x
本帖最后由 影-死神 于 2018-10-11 23:05 编辑

时间复杂度的定义
算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,
使得T(n)/f(n)的极限值(当n趋近于无穷大时)为不等于零的常数,则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度

时间复杂度的数量级(升序)
1、log2n、 n、 n*log2n、n2、n3、2n、n!、nn

简易判断方法
只有顺序执行,没有循环和递归等则时间复杂度为1
如果有二分时间复杂度为O(log2n),二分例如快速幂、二分查找;
如果算法中存在for循环,则看有几重for循环:
只有一重时间复杂度为O(n)
二重时间复杂度为O(n2),依此类推......
如果一个for循环套一个二分,那么时间复杂度则为O(n*logn)
简单的二分递归时间复杂度为2n
二分递归即每次递归分成两份分别递归,并且递归变量相对于上次递归减少1。

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2018-12-15 11:59

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表