大 O 表示法：时间复杂度

Java 代码优化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

什么是时间复杂度？

时间复杂度：度量运行时间随输入规模的增长
帮助回答："数据增大 10× 会怎样？"
不关注绝对时间

大 O 表示法

用于描述最坏情况的数学记号。

常见复杂度类别：

O(1): 常数时间——与规模无关

理解 O(1)

ArrayList 的 get() 是 O(1) 的示例

持有 String 的 ArrayList 的内部（简化）实现：

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

大 O 表示法

用于描述最坏情况的数学记号

常见复杂度类别：

O(1): 常数时间——与规模无关
O(n): 线性时间——随输入规模增长

理解 O(n)

类似示例：ArrayList 的 contains()

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

大 O 表示法

用于描述最坏情况的数学记号

常见复杂度类别：

O(1): 常数时间——与规模无关
O(n): 线性时间——随输入规模增长
O(n²): 二次时间——随规模二次增长

二次复杂度的实用示例

// Finding a pair of numbers that sum to a target value
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

为何关注时间复杂度

输入规模的影响：

O(1): 1,000 -> 1,000,000 项 = 用时不变！
O(n): 1,000 -> 1,000,000 项 = 慢 1,000×
O(n²): 1,000 -> 1,000,000 项 = 慢 1,000,000×

2025-05-10 2:27:06 PM 的截图

¡Vamos a practicar!

Java 代码优化