时间复杂度

2020-09-12 本文已影响0人每天学习135个小时

设 $n$ 为问题规模. 当 $n$ 趋于无穷时, 若程序执行的次数 $T(n)$ 与 $f(n)$ 为同阶的无穷大, 则称算法的时间复杂度 $T(n) = O(f(n))$

时间复杂度的求法: 对于一段代码, 设执行完毕需要m步, 然后设法寻找m与问题规模 n之间的等量关系(利用循环的边界条件). 示例如下

def fun(n):
    i = 0
    while n >= (i+1)**2:
        i += 1

分析设执行完毕需要m次. 第m次时 $(m+1)^2$ 略小于 $n$ , 引入一个起修正作用的常数 $C$ , 有 $(m+1)^2+C = n,$ 即 $m+1 \approx \sqrt n,$ 也就是说时间复杂度为 $O(\sqrt n)$

参考资料

时间复杂度十道练习题目

https://www.cnblogs.com/wangzheming35/p/12929095.html
时间复杂度和空间复杂度，大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