程序和算法的时间复杂度

• 一个程序或算法的时间效率，也称“时间复杂度”，有时简称“复杂度”
• 复杂度常用大的字母 O 和小写字母 n 来表示，比如 O( n ) , O( n ^ 2 ) 等。n 代表问题的规模。
• 时间复杂度是算法运行过程中，某种时间固定的操作需要被执行的次数和 n 的关系来衡量的。例如，在无序数列中查找某个数，复杂度是 O ( n )。
• 计算复杂度的时候，只统计执行次数最多的（当 n 足够大时）那种固定操作的次数。比如某个算法需要执行加法 n ^ 2 次，除法 n 次，那么就记其复杂度是 O（n ^ 2）的。

<aside> ⚠️ 无序数列中查找某个数，需要操作平均 n / 2 次，但是考虑复杂度时不看系数，只看指数。

</aside>

• 复杂度有“平均复杂度”和“最坏复杂度”两种，两者可能一致，也可能不一致。例如快速排序。一般情况下平均复杂度足够高就可以，同时也要保证算法能达到理想情况下的最坏复杂度。

• 如果复杂度是多个 n 的函数之和，则只关心随 n 增长最快的那个函数。

• 复杂度的分类：常数复杂度、对数复杂度、线性复杂度、多项式复杂度、指数复杂度、阶乘复杂度。