算法的时间复杂度
创作不易，请珍惜，之后会持续更新，不断完善
个人比较喜欢做笔记和写总结，毕竟好记性不如烂笔头哈哈，这些文章记录了我的IOS成长历程，希望能与大家一起进步
温馨提示：由于简书不支持目录跳转，大家可通过command + F 输入目录标题后迅速寻找到你所需要的内容
目录
- 一、估算代码执行次数
- 二、时间复杂度大O表示法
- 三、常见的算法算法复杂度
- 四、评价算法的时间复杂度
对于实现每个开发者都有自己的想法，但并不是每一个算法都会得到很好的应用和推广，受限于运行环境和运行时间的要求，总是会有一些算法虽然也能够得到想要的结果但是终究会被摒弃，而评价一个算法好坏的一个重要标准就是算法的时间复杂度。
一、估算代码执行次数
事实上对于算法来讲，获取某一组数据的精确执行时间并没有太大的意义，而且也完全没有必要，只需要预估算法需要代码的指令数量量级就可以大致知道算法需要消耗的相对时间。一般情况下，执行次数少的算法肯定要比执行次数多的花费更少的时间，这样既可以简化时间复杂度的评定标准，又能快速的对两个算法的优劣作出评估。
栗子1
int test(int n) {
if (n > 80) {
printf("Excelent");
} else if (n > 60) {
printf("Good");
} else {
printf("Bad");
}
for (int index = 0; index < n; index++) {
printf("Execute once");
}
}
if…else…结构中，只需要判断执行一次，输出执行一次，指令总共执行1+1=2次。在for结构中，初始化赋值index=0执行一次，在之后的循环中，index每取一个值，比较执行一次，循环体执行一次，自增运算执行一次，共执行三次，而循环结构需要循环n次，所以需要执行1+3 * n = 3n + 1次。所以对于上边的方法来讲，假设指令执行的时间一样，就可以大概得出方法一共需要执行指令=3+3n次。
栗子2
void test(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("Execute once");
}
}
}
最外层循环，初始化赋值i一次，对于每一次循环i参与比较一次，自增一次，循环体执行一次,所以针对外层循环来讲，时间复杂度O(n) =1+n+n+n*(循环体)。而对于内层循环来讲，初始化赋值j一次，对于每一次循环j参与比较一次，自增一次，循环体执行一次，所以内层循环的时间复杂度=1+n+n+n。所以总的时间复杂度=1+n+n+n*(1+n+n+n) = 1+2n+n*(3n+1) = 3n²+3n+1。
栗子3
void test(int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
printf("Execute once");
}
}
}
对于内层循环来讲，对于每一个i值，内层需要执行的指令数Q(n)=1+(n−i)+(n−i)+(n−i)=1+3(n−i)。对于外层循环来讲，每一次循环需要指令指令的次数为Q(n)，所以需要将i依次代入Q(n)中进行求和F(n) = ₀∑ⁿ⁻¹ Q(i) = 1+3n+1+3(n−1)+...+1+3(n−(n−1)) = n + 3₁∑ⁿj = 3n²/2 − n/2。
栗子4
void test(int n) {
while((n = n / 2) > 0) {
printf("Execute once");
}
}
在每次while循环中，n都会被折半，相当于以2为底的对数，因此n = n / 2这个操作会执行 log₂n次，同样的条件判断也需要执行 log₂n次，循环也需要执行 log₂n次，所以该方法一共需要执行指令此时F(n) = log₂n + log₂n + log₂n = 3log₂n。
栗子5
void test5(int n) {
int a = 10;
int b = 20;
int c = a + b;
int *arr = (int *)malloc(sizeof(n));
for (int i = 0; i < n; i++) {
printf("Execute once");
}
}
a,b,c赋值各执行一次，数组初始化执行一次。for循环中，初始化赋值i一次，i参与比较操作n次，i自增运行n次，循环体执行n次，所以方法共执行指令的次数 F(n)=4+1+3n=3n+5。
栗子6
void test (int n) {
for (int i = 0; i < n;i *= 2) {
for (int j = 0; j < n; j++) {
printf("Execute once");
}
}
}
内层循环中，初始化赋值j执行一次，每一次内层循环中j参与比较一次，自增一次，内层循环体执行一次，所以针对每一次外循环内层需要执行指令数Q(n)=1+n+n+n=3n+1。
在外层循环中，初始化赋值i一次，每次 i = i ∗ 2，相当于以2为底数的指数递增，所以 i ∗ = 2共执行log₂n次，所以i参与比较的次数为log₂n，外层循环体执行的次数log₂n。
所以该函数一共执行指令数F(n) = 1+ log₂n + log₂n + log₂n ∗ Q(n) = 1 + 3log₂n + 3nlog₂n。
二、时间复杂度大O表示法
在上边的例子中，使用了 n 的函数来表示指令执行的次数来描述算法的时间复杂度。而在实际估算算法时间复杂度的过程中，常数的影响几乎是可以忽略的，只需要关心算法中关于规模 n 的数量级即可大致描述算法的优劣。算法的时间复杂度通常用O表示，定义为T(n)=O(F(n))。大O表示法只关注算法关于规模的n的量级，所以具有以下特征：
- 忽略表达式的常数，系数以及低阶项
- 忽略常数：如果有关于
n的项，可以直接忽略表达式中的常数项；如果不包含任何关于n的项，则算法的时间复杂度为O(1); - 忽略系数： 在关于
n的表达式中，只需要关心n的量级，系数可以忽略为1；所以在O表示法中，F(n) = 3n与F(n) = n具有同样的时间复杂度; - 忽略低阶项：由于
O表示法是一个只关注关于n量级的算法复杂度表示法，所以如果存在关于n更高量级的项，则底量级的项可以忽略。例如F(n) = 1 + 3log₂n + 3nlog₂n 可以表示为F(n) = nlog₂n`。 - 对数阶忽略底数：由于在对数运算中，任意对数底都可以通过乘以指定常数转化为任意指数底，例如：
log₉n = log₂n / log₂9，所以底数并不影响算法的量级，因此对数阶时间复杂度可以忽略算法的底数。
大O分析法只是一种在不执行运算的前提的下粗略估算算法时间复杂度的一种方。由于算法在不同场景下表现出的耗时并不相同，所以时间复杂度多数指最坏的复杂度。
三、常见的算法算法复杂度
| 执行次数 | 复杂度 | 非正式术语 |
|---|---|---|
| 常数 | O(1) | 常数阶 |
| 3n+5 | O(n) | 线性阶 |
| 3n²+3n+1 | O(n²) | 平方阶 |
| 3log₂n | O(log₂n) | 对数阶 |
| 1 + 3log₂n + 3nlog₂n | O(nlog₂n) | nlogn阶 |
| 3n³+3n+3 | O(n³) | 立方阶 |
| 2ⁿ | O(2ⁿ) | 指数阶 |
当 n 逐渐增大时，算法时间复杂度：O(1) < O(log₂n < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)。随着 n的增大，O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)阶的算法复杂度会快速的增加，所以应该尽可能优化或者摒弃这种阶的算法复杂度。
四、评价算法的时间复杂度
通过使用大 O O O时间复杂度表示法可以快速的预估一个算法的时间复杂度，通过对比不同算法对同一问题实现的时间复杂度即可对算法的优劣作出初步的判断.
例如：需要求出1～100的自然数和
算法1：可以尝试使用递归来处理
int sum(int n) {
if (n == 1) {
return 1;
}
return n + sum(n-1);
}
在每次递归中，首先要判断一次，如果 n = 1 则会直接返回，否则需要执行一次n + sum(n-1)，需要一共需要判断n次，进行加法操作n−1次（最后一次当 n=1时直接返回）。即F(n)=n+n−1=2n−1。所以时间复杂度为：O(n)=O(F(n))=O(n)。
算法 2: 可以采用著名的高斯定理
int sum = n * (n + 1) / 2
这样的话算法的时间复杂度就变成了常数级的运算，时间复杂度变为：O(n)=O(1)。通过两种算法时间复杂度的比较，由于 O(1)<O(n)，所以使用算法2比使用算法1更加具有优势。
在尽可能的情况下，需要对算法的时间复杂度和空间复杂度进行优化，以实现尽可能小的时间复杂度和尽可能小的空间复杂度。事实的多数情况是，你只能牺牲其中的一种复杂度来成就另一种复杂度，以时间换空间或者以空间换时间。
