使用这套工具来进行算法的评估

2018-07-01  本文已影响8人  夕阳下的不回头

复杂度的分析和界定是我们分析的重点

级数:

收敛级数  每一项都递减的足够快使得级数和有一个确定的上界

再变化

内循环步长变大   但是这仍是线性增长 我们可以将坐标轴压缩 

画出图像  发现 内循环步长变大并不足以改变这个算法的复杂度和阶数

相当于把原来的复杂度除以2013 并不足以影响渐进复杂度

再变化 外循环的步长不再是线性增长 每次乘以2

那个2^[log2(n-1)]  这个中括号是向下取整的意思

代表着这个级数所能到达的最大项

这就像个啥 这个级数理论上最大项是n

但是你只能通过给定的形式(2的幂次)去逼近n

最终也不能超过n 所以 最后一项才写成这个2^[log2(n-1)] 

课后练习:

时间复杂度  关心的是执行基本操作的次数!!!!!

上一篇下一篇

猜你喜欢

热点阅读