文章目录[隐藏]
算法定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。描述解决问题的方法。
算法的五个基本特性:
算法设计的要求：
算法效率的度量方法：
事后统计方法: 这种方法主要是通过设计好的测试程序和数据，利用计算机计时 器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。事前分析估算方法: 在计算机程序编制前，依据统计方法对算法进行估算。
函数的渐近增长：
判断一个算法的效率时，函数中的常数和其他次项常常可以忽略，而更应该关注主项（最高阶项）的阶数。
假设有一个算法的时间复杂度为：T(n) = 3n² + 5n + 10
- 当 n 很大时，n² 项的增长速度远远快于 n 和常数项。
- 因此，3n² + 5n + 10 的渐近增长率主要由 n² 决定。
- 判断算法效率时，可以忽略常数和低阶项，只关注最高阶项。
- 所以，T(n) 的渐近时间复杂度为 O(n²)。
算法的时间复杂度：
常见的时间复杂度：
| 执行次数函数 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n²+2n+1 | O(n²) | 平方阶 |
| 5log₂n+20 | O(log n) | 对数阶 |
| 2n+3nlog₂n+19 | O(nlog n) | nlogn阶 |
| 6n³+2n²+3n+4 | O(n³) | 立方阶 |
| 2ⁿ | O(2ⁿ) | 指数阶 |
时间从小到大：
O(1) < O(log n) < O(n) < O(nlog n)示例：
int sum(int a[], int n) {
int s = 0; // 1次
for (int i = 0; i < n; i++) { // n次
s += a[i]; // n次
}
return s; // 1次
}步骤分析：
int s = 0;执行1次for (int i = 0; i < n; i++)循环n次s += a[i];每次循环执行1次，共n次
return s;执行1次
总执行次数：1 + n + n + 1 = 2n + 2
推导大O阶：
- 忽略常数项和低阶项，只保留最高阶项
- 2n + 2 ≈ n
所以，时间复杂度为 O(n)
算法空间复杂度
算法空间复杂度是指算法在运行过程中所需存储空间的度量，它反映了算法占用内存空间的多少。通常用大O符号表示，描述的是输入规模 n 增大时，算法所需额外空间的增长趋势。空间复杂度越低，算法越节省内存资
示例:
- O(1) 空间复杂度（常数空间）
int sum(int a[], int n) {
int s = 0;
for (int i = 0; i < n; i++) {
s += a[i];
}
return s;
}- 只用了一个整型变量
s，不管输入n多大，所需额外空间不变，空间复杂度为 O(1)。
- O(n) 空间复杂度（线性空间）
int* copy_array(int a[], int n) {
int* b = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
b[i] = a[i];
}
return b;
}- 需要额外分配一个长度为 n 的数组，空间复杂度为 O(n)。
