常见的时间复杂度

C++中的时间复杂度是指算法执行时间随输入数据规模增长的变化趋势，它用来描述算法的效率。时间复杂度通常用大O表示法来表示，它描述了算法运行时间的上界。以下是一些常见的时间复杂度及其对应的C++代码示例：

1. 常数时间复杂度 O(1)：算法的运行时间不随输入规模的变化而变化。

   int constantTimeFunction() {return 1;
   }
   

2. 线性时间复杂度 O(n)：算法的运行时间与输入规模成正比。

   void linearTimeFunction(int n) {for (int i = 0; i < n; ++i) {// 操作}
   }
   

3. 对数时间复杂度 O(log n)：通常出现在二分搜索等算法中。

   void logarithmicTimeFunction(int n) {while (n > 1) {n /= 2;// 操作}
   }
   

4. 线性对数时间复杂度 O(n log n)：如快速排序的平均情况。

   void linearLogarithmicTimeFunction(int n) {for (int i = 0; i < n; ++i) {// 假设每次操作的时间复杂度为O(log n)}
   }
   

5. 平方时间复杂度 O(n^2)：如冒泡排序。

   void quadraticTimeFunction(int n) {for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {// 操作}}
   }
   

6. 立方时间复杂度 O(n^3)：如三重循环的算法。

   void cubicTimeFunction(int n) {for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {for (int k = 0; k < n; ++k) {// 操作}}}
   }
   

7. 指数时间复杂度 O(2^n)：如暴力搜索。

   void exponentialTimeFunction(int n) {for (int mask = 0; mask < (1 << n); ++mask) {// 操作}
   }
   

8. 阶乘时间复杂度 O(n!)：如排列问题。

   void factorialTimeFunction(int n) {for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (j != i) {for (int k = 0; k < n; ++k) {if (k != i && k != j) {// 操作}}}}}
   }
   

时间复杂度排名

以下是按照时间复杂度从低到高排序的表格，展示了不同时间复杂度类别的排序算法：

时间复杂度类别	排序算法
O(1)	桶排序（Bucket Sort）在特定条件下，计数排序（Counting Sort）在特定条件下
O(n)	桶排序（Bucket Sort）一般情况，计数排序（Counting Sort）一般情况，基数排序（Radix Sort）
O(n log n)	归并排序（Merge Sort），快速排序（Quick Sort）平均情况，堆排序（Heap Sort），希尔排序（Shell Sort）平均情况
O(n^2)	插入排序（Insertion Sort），选择排序（Selection Sort），冒泡排序（Bubble Sort）
O(2^n)	递归排序算法（如递归分治但每次分解没有显著减少问题的规模）
O(n!)	旅行商问题（Traveling Salesman Problem, TSP）的暴力解法

说明：

• 这个表格主要展示了理论上的时间复杂度，实际性能可能会有所不同。
• 快速排序的平均时间复杂度是 O(n log n)，但最坏情况下是 O(n^2)。通过随机化选择基准元素等技术可以避免最坏情况。
• 希尔排序的平均时间复杂度依赖于间隔序列的选择，因此没有给出具体的复杂度。
• 桶排序和计数排序在特定条件下可以达到 O(n) 的时间复杂度，但它们通常需要额外的空间。
• 基数排序的时间复杂度是 O(nk)，其中 k 是数据的基数（例如，对于整数，k 是最大数的位数）。