时间复杂度计算分类

本次知识想记录一下学习数据结构与算法分析中的知识：算法级数快速计算。

分类

多项式级数，时间复杂度与多项式中最高次幂同级。例如：
$T(n)= a^2 + b + 2c^3 = O(n^3)$ 的时间复杂度:$O(n^3)$

指数级，时间复杂度与其末项同阶。通向式：
$T(a^n) = a^0 + a^1 + … + a^n = O(a^n) $

算数级数，时间复杂度与末项平方同阶。通向式：
$T(n) = 1 + 2 + 3 + … + n = O(n^2)$

幂方级数，时间复杂度，比幂次高出一阶。通项公式：
$T(n^2) = 1^2 + 2^2 + … + n^2 = O(n^3)$

收敛级数，时间复杂度近似$O(1)$。例如：
$\frac{1}{\frac{1}{2}} + \frac{1}{\frac{2}{3}} + … + \frac{1}{\frac{n-1}{n}} = O(1)$

调和级数，时间复杂度的通项公式为：
$h(n) = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + … + \frac{1}{n} = ø(logn) $

对数级数，时间复杂度的通项公式为：
$T(n) = log1 + log2 + … + log n = log(n!) <= O(n·logn)$