C++算法分析基础

算法分析主要评估算法的性能，这在优化程序效率时至关重要。关键指标之一是时间复杂度，它衡量随着输入规模增长，算法执行时间的变化趋势。

排序算法分析与时间复杂度

排序算法用于将一组无序的数据元素按特定顺序排列。常见的排序算法有冒泡排序、插入排序、选择排序、归并排序和快速排序等，它们各有不同的时间复杂度：

• 冒泡排序：通过多次比较相邻元素并交换，把最大（或最小）的元素逐步“冒泡”到数组末尾。它的时间复杂度是 $O(n^2)$，因为对于有 $n$ 个元素的数组，需要进行大约 $n^2$ 次比较操作。
• 插入排序：将一个数据插入到已经排好序的数组中的适当位置。在最坏情况下，每次插入都要移动数组中的大部分元素，时间复杂度同样是 $O(n^2)$；但在最好情况下（数组已经有序），时间复杂度为 $O(n)$。
  

递归的终止

递归函数在自身内部调用自身，但必须有终止条件，否则会陷入无限递归。例如，计算阶乘的递归函数：

int factorial(int n) {if (n == 0 || n == 1) {  // 终止条件return 1;}return n * factorial(n - 1);
}

当 n 为 0 或 1 时，函数直接返回 1，不再进行递归调用，从而防止程序栈溢出。

标准的算法复杂度类别

常见的算法复杂度类别有：

• 常数时间复杂度 $O(1)$：算法执行时间不随输入规模增长而变化，例如访问数组中的单个元素：int num = arr[0];。
• 对数时间复杂度 $O(\log n)$：典型的如二分查找，每次将搜索区间减半，随着输入规模 $n$ 增大，执行时间增长缓慢。
• 线性时间复杂度 $O(n)$：遍历一次数组的操作，如计算数组元素之和：int sum = 0; for(int num : arr) sum += num; 。
• 线性对数时间复杂度 $O(n\log n)$：高效排序算法如归并排序、快速排序的平均时间复杂度为此类。
• 平方时间复杂度 $O(n^2)$：像冒泡排序、插入排序的最坏情况复杂度。
• 指数时间复杂度 $O(2^n)$：递归求解斐波那契数列的朴素算法就属于这类，效率极低。

快速排序算法

快速排序采用分治策略，是一种高效的排序算法，平均时间复杂度为 $O(n\log n)$。

#include <iostream>
#include <vector>// 划分函数，选择一个基准元素，将数组分为两部分
int partition(std::vector<int>& arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; ++j) {if (arr[j] <= pivot) {++i;std::swap(arr[i], arr[j]);}}std::swap(arr[i + 1], arr[high]);return i + 1;
}// 快速排序主体函数
void quickSort(std::vector<int>& arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

int main() {std::vector<int> numbers = {10, 7, 8, 9, 1, 5};quickSort(numbers, 0, numbers.size() - 1);for (int num : numbers) {std::cout << num << " ";}return 0;
}

• 原理：partition 函数选定一个基准元素（这里选数组末尾元素），把数组分成两部分，左边部分元素小于等于基准，右边部分大于基准。然后递归地对左右两部分进行排序。
• 时间复杂度：在平均情况下，每次划分能把数组大致分成两半，递归深度为 $O(\log n)$，每层划分操作需要 $O(n)$ 时间，所以平均时间复杂度是 $O(n\log n)$；但在最坏情况下（例如数组已经有序，每次选的基准都是最值），时间复杂度会退化到 $O(n^2)$ 。

数学归纳法

数学归纳法用于证明与自然数有关的命题。步骤一般分为两步：

1. 基础步骤：证明当 $n=n_0$（通常 $n_0=0$ 或 $n_0=1$） 时命题成立。
2. 归纳步骤：假设当 $n=k$ 时命题成立，证明当 $n=k+1$ 时命题也成立。

以证明等差数列求和公式 $S_n=\frac{n(a_1+a_n)}{2}$ 为例：

• 基础步骤：当 $n=1$ 时，$S_1=a_1=\frac{1\times (a_1+a_1)}{2}$，公式成立。
• 归纳步骤：假设 $S_k=\frac{k(a_1+a_k)}{2}$ 成立，那么 $S_{k+1}=S_k+a_{k+1}=\frac{k(a_1+a_k)}{2}+a_{k+1}=\frac{(k+1)(a_1+a_{k+1})}{2}$，证毕。数学归纳法常用来证明算法的正确性，例如递归算法在不同输入规模下的有效性。
• 下面以证明等差数列求和公式 $S_n=\frac{n(a_1+a_n)}{2}$ 为例，展示一个用 C++ 编写的体现数学归纳法思路的代码实例：

#include <iostream>// 计算等差数列的和
int arithmeticSeriesSum(int n, int a1, int an) {return (n * (a1 + an)) / 2;
}int main() {// 基础情况验证int n1 = 1;int a1 = 1;int an1 = 1;int sum1 = arithmeticSeriesSum(n1, a1, an1);if (sum1 == (n1 * (a1 + an1)) / 2) {std::cout << "基础情况（n = 1）成立" << std::endl;} else {std::cout << "基础情况（n = 1）不成立" << std::endl;}// 归纳步骤验证int k = 5;int a1_k = 1;int an_k = k;int sum_k = arithmeticSeriesSum(k, a1_k, an_k);int k_plus_1 = k + 1;int a1_k_plus_1 = 1;int an_k_plus_1 = k + 1;int sum_k_plus_1 = arithmeticSeriesSum(k_plus_1, a1_k_plus_1, an_k_plus_1);if (sum_k + (a1_k_plus_1 + an_k_plus_1) == sum_k_plus_1) {std::cout << "归纳步骤成立" << std::endl;} else {std::cout << "归纳步骤不成立" << std::endl;}return 0;
}

在这段代码中：

• arithmeticSeriesSum 函数用于根据公式计算等差数列的和。
• 在 main 函数里，先验证基础情况，也就是当 n = 1 时，公式是否成立。随后，通过手动设定一个值 k 来模拟归纳步骤，假设 n = k 时公式成立，检验当 n = k + 1 时公式是否依然成立。实际应用中，数学归纳法常用于证明算法正确性，像递归算法的正确性证明，往往也遵循先证基础情况，再证归纳步骤的流程。
•