二. 算法

算法四大特性

1. 输入输出
2. 有穷性
3. 确定性
4. 可行性

设计算法四大要求

1. 正确性
2. 可读性
3. 健壮性
4. 时间效率高和存储量低

算法时间复杂度

推导大O阶方法:
1.用常数1取代运行时间中的所有加法常数。2. 在修改后的运行次数函数中，只保留最高阶项。3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常数阶

int sum = 0, n = 100;
sum = n / 2 * (n + 1); //执行一次，所以时间复杂度为O(1)
printf("%d", sum);

线性阶

int i, n;
for (i = 0; i < n; i++) {
  //取决于n的值，所以时间复杂度为O(n)
}

对数阶

int count = 1
while (count < n) {
   count = count * 2 //count的平方 = n，所以时间复杂度为O(logn)
}

平方阶

int i, j;
for (i = 0; i < n; i++) { //执行n次
    for (j = 0; j < n; i++) { //执行n次
            //时间复杂度为O(n²)
    }
}

常见的时间复杂度表

执行次数函数	阶	非正式术语
12	O(1)	常数阶
2n + 3	O(n)	线性阶
3n² + 2n + 1	O(n²)	平方阶
5㏒2n + 20	O(㏒n)	对数阶
2n + 3n㏒2n + 19	O(n㏒n)	n㏒n阶
6n³ + 2n² + 3n + 4	O(n³)	立方阶
2n	O(2n)	指数阶

常用时间复杂度所耗费的时间从小到大依次是: 0(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)