使用这套工具来进行算法的评估
2018-07-01 本文已影响8人
夕阳下的不回头
复杂度的分析和界定是我们分析的重点
级数:
收敛级数 每一项都递减的足够快使得级数和有一个确定的上界
再变化
内循环步长变大 但是这仍是线性增长 我们可以将坐标轴压缩
画出图像 发现 内循环步长变大并不足以改变这个算法的复杂度和阶数
相当于把原来的复杂度除以2013 并不足以影响渐进复杂度
再变化 外循环的步长不再是线性增长 每次乘以2
那个2^[log2(n-1)] 这个中括号是向下取整的意思
代表着这个级数所能到达的最大项
这就像个啥 这个级数理论上最大项是n
但是你只能通过给定的形式(2的幂次)去逼近n
最终也不能超过n 所以 最后一项才写成这个2^[log2(n-1)]
课后练习:
时间复杂度 关心的是执行基本操作的次数!!!!!