首页 > 代码库 > 算法复杂度分析

算法复杂度分析

算数级数:与末项平方同阶

T(n) = 1+2+…+n = n(n+1)/2 = O(n2)

幂方级数:比幂次高出一阶

T2(n) = 12 + 22 + 32 + … + n2 = n(n+1)(2n+1)/6 = O(n3)

T3(n) = 13 + 23 + 33 + … + n3 = n2(n+1)2/4 = O(n4)

T4(n) = 14 + 24 + 34 + … + n4 = n(n+1)(2n+1)(3n2 + 3n -1)/30 = O(n5)

几何级数(a > 1):与末项同阶

Ta(n) = a0 + a1 + … + an = (an+1 -1)/(a - 1) = O(an)

1 + 2 + 4 + … + 2n = 2n+1 - 1 = O(2n+1) = O(2n)

收敛级数

1/1/2 + 1/2/3 + 1/3/4 + … + 1/(n-1)/n = 1 - 1/n = O(1)

1 + 1/22 + … + 1/n2 < 1 + 1/22 + … = π2/6 = O(1)

1/3 + 1/7 + 1/8 + 1/15 + 1/24 + 1/26 + 1/31 + 1/35 + … = 1 = O(1)

可能未必收敛,但是长度有限

调和级数 : h(n) = 1 + 1/2 + 1/3 + … + 1/n = O(log(n))

对数级数 : log(1) + log(2) + log(3) + … + log(n) = log(n!) = O(nlog(n))

算法复杂度分析