时间复杂度
上一节已经讲了时间复杂度的概念，就是用来衡量算法随着问题规模增大，算法执行时间增长的快慢的一个函数。
这里不再赘述，先来串代码，下边开始时间复杂度的计算：
int sum = 0;
# 执行 1 次
for(int i = 0; i <= n; i++){
# i = 0 执行一次
# i <= n 执行 n + 2 次
# i++ 执行 n +1 次
# i==0时 1 次
# i==1时 2 次
# ……
# i==n时 n +1 次
# i==n+1时
# 本次执行i<=n 的判断时发现条件不成立，结束循环 n+2 次
# 所以 i <= n 执行 n + 2次
sum = sum +i;
# 执行 n +1 次
}
时间分析：
上边的算法一共执行了 1 + 1 + n + 2 + n + 1 + n +1 = 3n +6 个语句。
假设每个语句执行时间一致，均为常数 t，则总时间 T = (3n +6) * t。
随着规模 n 的增大，总时间的增长率与 n 的增长率一致，系数和常数可以省略掉，所以忽略 6 、3 、 t，时间复杂度为 O(n)。
- 复杂度是关于
增长率的，所以可以直接忽略常数项。- 一般可以直接关注循环体的执行次数，即示例中
sum = sum + i的执行次数。
单循环体时间复杂度计算
直接关注循环体的执行次数，设为 k。
以上边的代码为例，循环体执行次数： k = n + 1
忽略常数，时间复杂度为 O(n)。
再来个栗子：
int sum = 0;
for(int i = 0; i <= n; i = 2 * i){
sum = sum + i;
}
i 的取值： 1, 2, 4, 8…
设执行次数为 k，满足条件： <= n
当 k > n 时跳出循环，所以循环体执行次数为： [
n]
忽略常数、系数，故时间复杂度为 O(logn)
多循环体时间复杂度计算
for(int i = 1; i <= n; i++){
x++;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
x++;
}
}
两个循环体是独立的，所以用加法规则：
T(n) = T1(n) + T2(n) = max(T1(n),T2(n))
直接看第二个嵌套循环，可得出时间复杂度为 T(2n) = O()。
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j = 2 * j){
x++;
}
}
这里两个循环体是嵌套的，所以使用乘法规则，外边的循环体执行次数为 n + 1，里边的循环体执行次数为 n，所以时间复杂度为：T(n) = T1(n) * T2(n) = O(nlogn)
常用时间复杂度从大到小依次是：
O(1) < O() < O(n) < O(nlog) < O(
) < O(
) < O(
) < O(n!) < O(
)
空间复杂度
空间复杂度 S(n) 指算法运行过程中所使用的辅助空间的大小，记为： S(n) = O(f(n))。
辅助空间：
除了存储算法本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。原地工作：
算法所需要的辅助空间，常量，即 O(1)。所需要的空间大小是固定的，不随着算法的规模的改变而改变。
