时间复杂度

设 $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

时间复杂度(下)
时间复杂度知识点最好时间复杂度最坏时间复杂度平均情况复杂度均摊时间复杂度
day02 四种时间复杂度分析方法
一、时间复杂度有哪几种？最好时间复杂度最坏时间复杂度平均时间复杂度（概率）均摊时间复杂度（特殊的平均时间复...
数据结构与算法之美笔记——复杂度分析(下)
摘要：时间复杂度还可分为四种，分别是「最好时间复杂度」、「最坏时间复杂度」、「平均时间复杂度」和「均摊时间复杂度...
算法学习笔记-浅析时间复杂度
四种情况的维度：最好情况时间复杂度最坏情况时间复杂度平均情况时间复杂度均摊时间复杂度最好时间复杂度在最...
sort_algorithm
排序方法时间复杂度（平均）时间复杂度（最坏) 时间复杂度（最好) 空间复杂度稳定性复...
归并排序图解
平均时间复杂度：O(nlogn) 最佳时间复杂度：O(n) 最差时间复杂度：O(nlogn) 空间复杂度：O(n)...
时间复杂度和空间复杂度笔记
复杂度分析笔记复杂度主要分为时间和空间复杂度时间复杂度：算法（程序）执行的时间变化趋势空间复杂度：算法（程序...
归并排序 by Python
最好时间复杂度：O(n*logn)最坏时间复杂度：O(n*logn)平均时间复杂度：O(n*logn)空间复杂度：...
day09-冒泡排序+优化
排序算法（SortAlgorithm）算法时间复杂度总结：排序方法时间复杂度（平均）时间复杂度（最坏）时间复杂...
时间复杂度和空间复杂度
时间复杂度如何理解算法时间复杂度 1.时间复杂度，表示形式为Big O notation 时间复杂度也可以理解为...