c++基础36时间复杂度-常见的时间复杂度

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) {
                           // 操作
                       }
                   }
               }
           }
       }
   }