时间复杂度
设 为问题规模. 当
趋于无穷时, 若程序执行的次数
与
为同阶的无穷大, 则称算法的时间复杂度
时间复杂度的求法: 对于一段代码, 设执行完毕需要m步, 然后设法寻找m与问题规模 n之间的等量关系(利用循环的边界条件). 示例如下
def fun(n):
i = 0
while n >= (i+1)**2:
i += 1
分析 设执行完毕需要m次. 第m次时 略小于
, 引入一个起修正作用的常数
, 有
即
也就是说时间复杂度为
参考资料
-
时间复杂度十道练习题目
-
时间复杂度和空间复杂度，大O表示法【数据结构和算法入门2】
https://www.bilibili.com/video/BV14j411f7DJ?from=search&seid=333313584522830031
-
【时间复杂度】听说你觉得时间复杂度很复杂？不妨听听我的理解
https://www.bilibili.com/video/BV18g4y1i729/?spm_id_from=333.788.videocard.0
