Big O 时间复杂度入门：算法效率一文搞懂

时间复杂度是衡量算法效率的标准。本文介绍 Big O 表示法。

什么是 Big O？

Big O 表示算法随输入规模增长的时间增长趋势。

常见时间复杂度

示例分析

O(1) - 常数时间

int getFirst(int[] arr) {
    return arr[0]; // 无论数组多大，都是1步
}

O(n) - 线性时间

int find(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

O(n²) - 平方时间

void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
        }
    }
}

O(log n) - 对数时间

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

空间复杂度

总结

理解时间复杂度是算法学习的基础。选择合适的算法，可以大幅提升程序性能。