当前位置：首页 > article >正文

c++基础36时间复杂度

article 2024/11/18 11:59:00

时间复杂度

常见的时间复杂度
时间复杂度排名

常见的时间复杂度

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

常数时间复杂度 O(1)：算法的运行时间不随输入规模的变化而变化。
```
int constantTimeFunction() {
    return 1;
}
```

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

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

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

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

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

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

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

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

立方时间复杂度 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) {
                // 操作
            }
        }
    }
}

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

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

阶乘时间复杂度 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）的暴力解法