第1个回答 2022-07-09
一个算法花费的时间与算法中语句的执行次数成正比，我们将算法中的语句执行次数称为语句频度或时间频度，记为 T(n) ， n 称为问题的规模.
在时间频度中，当 n 不断变化时，时间频度 T(n) 也会不断变化，但有时我们想知道随着问题的规模 n 的不断增加，运行时间呈现怎样的变化规律，为此，引入了时间复杂度.
图中4条曲线分别表示4种不同的执行次数表达式，从图中可以看出，只要最高项的阶数相同，4种表达式值受其他项的影响很小，随着n增大，几乎可以忽略不计，甚至可以忽略与最高项相乘的常数
最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会超过此时间.
常数阶O(1) 、 对数阶O(log₂n) 、 线性阶O(n) 、 线性对数阶O(nlog₂n) 、 平方阶O(n²) 、 立方阶O(n³) 、 k次方阶(n) 、 指数阶O(2ⁿ)