程序或算法的时间复杂度
- 一个程序或算法的时间效率,也称“时间复杂度”,有时简称“复杂度”
- 复杂度常用大写字母 O 和小写字母 n 来表示,比如 O(n), O(n²)等。n代表问题的规模
- 时间复杂度是用算法运行过程中,某种时间固定的操作需要被执行的次数和n的关系来衡量的,在无序数列中查找某个数,复杂度是O(n)
- 计算复杂度的时候,只统计执行次数最多的(n足够大时)那种固定操作的次数。比如某个算法需要执行加法n²次,除法n次,那么就记其复杂度是 O(n²)
- 复杂度有"平均复杂度"和"最坏复杂度"两种,两者可能一直,也可能不一致
如果复杂度是多个n的函数之和,则只关心随n的增长增长的最快的那个函数
- O(n³+n²) => O(n³)
- O(2^n+n³) => O(2^n)
- O(n!+3^n) => O(n!)
- 常数复杂度:O(1)
- 对数复杂度:O(log(n))
- 线性复杂度:O(n)
- 多项式复杂度:O(n^k)
k是一个常数
- 指数复杂度:O(a^n)
- 阶乘复杂度:O(n!)