算法简介：特性、性能分析与复杂度表示
算法是计算机科学的核心，是为解决特定问题而设计的一系列明确、可执行的步骤。一个高效的算法能显著提升程序性能，而理解算法的基本特性和性能分析方法，是设计和优化算法的基础。
算法的五大基本特性
算法必须满足以下五个核心特征，缺一不可：
- 有穷性
算法必须在有限步骤内结束，不能无限循环。例如，求解斐波那契数列的算法需在计算到第 n 项后终止，而不是永远运行。 - 确定性
算法的每一步操作必须无歧义，对于相同的输入，只能产生唯一的输出。例如，“将变量 a 的值增加 1” 是确定的，而 “将 a 的值稍微增加一点” 则不符合确定性。 - 输入
算法可以有0 个或多个输入（从外部获取的数据）。例如，计算两个数的和需要 2 个输入，而打印 “Hello World” 则不需要输入。 - 输出
算法必须有1 个或多个输出（与输入相关的结果）。输出是算法解决问题的体现，例如排序算法的输出是有序数组。 - 可行性
算法的每一步操作必须能够通过有限次基本运算实现（如算术运算、逻辑判断等）。例如，“一步登天” 在现实中不可行，同理算法中不能包含无法执行的步骤。
算法性能分析：时间与空间复杂度
评价算法的优劣主要看其对时间和空间资源的占用，即时间复杂度和空间复杂度。它们不依赖具体硬件环境，而是通过数学模型描述算法的效率。
时间复杂度（Time Complexity）
时间复杂度表示算法执行时间随问题规模（通常用n表示）增长的变化趋势，使用大 O 符号（O notation） 表示。
核心思想：
- 忽略具体执行时间（受硬件、编程语言影响），仅关注基本操作的执行次数。
- 只保留影响趋势的最高阶项，并忽略系数和低阶项。
推导大 O 阶的步骤：
- 用常数 1 取代所有加法常数（如
f(n) = 3→O(1)）。 - 只保留最高阶项（如
f(n) = n² + 2n + 1→ 保留n²）。 - 若最高阶项系数不为 1，去除系数（如
f(n) = 2n³→O(n³)）。
常见时间复杂度及示例：
| 复杂度 | 名称 | 示例场景 | 执行次数与 n 的关系 |
|---|---|---|---|
| O(1) | 常数阶 | 基本运算（如变量赋值、算术运算） | 执行次数固定（与 n 无关） |
| O(logn) | 对数阶 | 二分查找 | 执行次数随 n 增长但增速极慢（log₂n） |
| O(n) | 线性阶 | 线性查找、单循环 | 执行次数与 n 成正比 |
| O(nlogn) | 线性对数阶 | 快速排序、归并排序 | 执行次数为n×log₂n |
| O(n²) | 平方阶 | 嵌套循环（如冒泡排序） | 执行次数与 n 的平方成正比 |
| O(2ⁿ) | 指数阶 | 递归求解斐波那契数列（未优化） | 执行次数随 n 呈指数增长（效率极低） |
示例解析：
常数阶（O (1)）：
1
2int sum = 0;
sum = (1 + 100) * 100 / 2; // 固定步骤，与n无关执行次数为 1，时间复杂度为
O(1)。线性阶（O (n)）：
1
2
3for (int i = 0; i < n; i++) {
System.out.println(i); // 执行n次
}执行次数为
n，时间复杂度为O(n)。对数阶（O (logn)）：
1
2
3
4int count = 1;
while (count < n) {
count *= 2; // 每次翻倍，执行log₂n次
}执行次数为
log₂n，时间复杂度为O(logn)（忽略对数底，因底为常数时可转换为系数）。平方阶（O (n²)）：
1
2
3
4
5for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(i + j); // 执行n×n次
}
}执行次数为
n²，时间复杂度为O(n²)。
空间复杂度（Space Complexity）
空间复杂度表示算法运行时所需存储空间随问题规模n增长的变化趋势，同样用大 O 符号表示。
关注的存储空间：
- 算法本身的指令集（固定，忽略）。
- 输入数据（问题本身决定，忽略）。
- 额外开辟的空间（如变量、数组、栈帧等，随算法变化）。
常见空间复杂度及示例：
| 复杂度 | 名称 | 示例场景 | 额外空间与 n 的关系 |
|---|---|---|---|
| O(1) | 常数阶 | 仅使用固定数量的变量 | 空间固定（与 n 无关） |
| O(n) | 线性阶 | 创建大小为 n 的数组 | 空间与 n 成正比 |
| O(n²) | 平方阶 | 创建 n×n 的二维数组 | 空间与 n 的平方成正比 |
| O(logn) | 对数阶 | 递归调用（栈深度为 logn） | 空间随 logn 增长 |
示例解析：
常数阶（O (1)）：
1
2int a = 1, b = 2;
int c = a + b; // 仅使用3个变量，空间固定额外空间为常数，空间复杂度为
O(1)。线性阶（O (n)）：
1
int[] arr = new int[n]; // 创建大小为n的数组
额外空间为
n，空间复杂度为O(n)。递归的空间复杂度：
1
2
3
4
5// 递归计算n的阶乘，递归深度为n
int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}递归栈的深度为
n，空间复杂度为O(n)