C语言常见算法和复杂度

C语言作为一种广泛使用的编程语言，提供了许多常见算法和相应的复杂度分析。以下是一些常见的算法及其复杂度：

1. **排序算法**：
- **冒泡排序（Bubble Sort）**：通过重复交换相邻未按顺序排列的元素来排序。时间复杂度为O(n^2)。
- **选择排序（Selection Sort）**：每次选择最小（或最大）的元素，放到已排序序列的末尾。时间复杂度为O(n^2)。
- **插入排序（Insertion Sort）**：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。时间复杂度为O(n^2)。
- **快速排序（Quick Sort）**：通过一个枢轴元素将数组分成两部分，然后递归地对这两部分进行排序。时间复杂度平均为O(n log n)，最坏情况下为O(n^2)。
- **归并排序（Merge Sort）**：将数组分成两半，分别排序后再合并。时间复杂度为O(n log n)。

2. **搜索算法**：
- **线性搜索（Linear Search）**：从数组的第一个元素开始，逐个检查直到找到目标元素。时间复杂度为O(n)。
- **二分搜索（Binary Search）**：在有序数组中，通过反复将搜索范围减半来查找目标元素。时间复杂度为O(log n)。

3. **图算法**：
- **深度优先搜索（DFS）**：从图的某个顶点开始，访问所有可达的顶点。时间复杂度为O(V + E)，其中V是顶点数，E是边数。
- **广度优先搜索（BFS）**：从图的某个顶点开始，逐层访问所有可达的顶点。时间复杂度为O(V + E)。
- **迪杰斯特拉算法（Dijkstra's Algorithm）**：用于计算单源最短路径。时间复杂度为O(V^2)，使用优先队列优化后可达到O((V + E) log V)。
- **弗洛伊德算法（Floyd-Warshall Algorithm）**：用于计算所有顶点对之间的最短路径。时间复杂度为O(V^3)。

4. **动态规划**：
- **斐波那契数列**：通过递归或迭代计算斐波那契数列。时间复杂度分别为O(2^n)和O(n)。
- **背包问题**：通过动态规划解决0/1背包问题。时间复杂度为O(nW)，其中n是物品数量，W是背包容量。

5. **数据结构相关算法**：
- **堆排序（Heap Sort）**：利用堆这种数据结构进行排序。时间复杂度为O(n log n)。
- **哈希表操作**：插入、查找和删除操作平均时间复杂度为O(1)。

这些算法在不同的应用场景中各有优劣，选择合适的算法可以显著提高程序的效率和性能。