L5_02 算法复杂度

一、含多项式的算法复杂度

1.1 O(n) 线性复杂度

// 遍历数组一次
void linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            cout << "找到目标" << endl;
            return;
        }
    }
}

1.2 O(n²) 平方复杂度

// 嵌套循环
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

1.3 O(n³) 立方复杂度

// 三重循环
void matrixMultiply(int A[][3], int B[][3], int C[][3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

---

二、含对数的算法复杂度

2.1 O(log n) 对数复杂度

// 二分查找
int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

2.2 O(n log n) 线性对数复杂度

// 快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

2.3 O(log log n) 双对数复杂度

// 某些优化算法
int find(int x) {
    while (x > 1) {
        x = sqrt(x);
    }
    return x;
}

---

三、复杂度比较

3.1 增长速度对比

复杂度	n=10	n=100	n=1000
O(1)	1	1	1
O(log n)	3	7	10
O(n)	10	100	1000
O(n log n)	30	700	10000
O(n²)	100	10000	1000000
O(2ⁿ)	1024	10³⁰	10³⁰⁰

3.2 复杂度排序（从小到大）

1. O(1)
2. O(log log n)
3. O(log n)
4. O(n)
5. O(n log n)
6. O(n²)
7. O(n³)
8. O(2ⁿ)
9. O(n!)

---

四、空间复杂度

4.1 O(1) 常数空间

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

4.2 O(n) 线性空间

int* copyArray(int arr[], int n) {
    int *newArr = new int[n];
    for (int i = 0; i < n; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

4.3 O(n²) 平方空间

int** createMatrix(int n) {
    int **matrix = new int*[n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new int[n];
    }
    return matrix;
}

---

五、示例程序

#include <iostream>
#include <cmath>
using namespace std;

// 计算复杂度示例
int main() {
    int n = 1000;
    
    // O(n)
    for (int i = 0; i < n; i++) {
        // 操作
    }
    
    // O(n²)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 操作
        }
    }
    
    // O(log n)
    int x = n;
    while (x > 1) {
        x = x / 2;
    }
    
    return 0;
}