该文大部分内容参考了博客:算法导论------递归算法的时间复杂度求解
算法设计与分析
从算法是否递归调用来分析，我们可以大致將算法分为递归算法与非递归算法。非递归算法时间复杂度分析较为简单，通常是计算算法中基本语句执行次数，一般都是一个关于问题规模n的表达式，然后用渐近符号Θ、O、o、Ω、ω表示出算法的时间复杂度。
递归算法是采用分治的方法，把一个“大问题”分解出若干个相似的“小问题”求解。在分析算法复杂度时，关键是根据递归过程建立递推关系式，然后求解递推关系式，得到算法执行的时间表达式（一般都与问题规模n相关），最后用渐近符号Θ、O、o、Ω、ωΘ、Ο、o、Ω、ω表示出算法的时间复杂度。
非递归算法时间复杂度分析
O(1)
如果算法的执行时间不随着问题规模n的增加而增长，它的基本语句执行的次数是固定的，总的时间由一个常数来限界。此类算法的时间复杂度是$O(1)$.
O(n)-O(n^m)
当有若干个循环语句时，时间复杂度是由嵌套层数最多的循环语句中的基本语句的执行次数决定.
Example:
void fun(int n) {
int x = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
for (int k = 1; k <= j; k++) {
x++; //基本语句
}
}
}
}
$f(n) = \sum{i=1}^n\sum{j=1}^i\sum{k=1}^j1 = \sum{k=1}^j\frac{i(i+1)}{2} = ... = O(n^3)$
在计算过程中会使用到一些多项式的求和技巧知识。
