一、时间复杂度与数据规模的对应关系
（以单核CPU每秒处理 (10^6) 次操作为基准）
| 数据规模(n) | 可接受的时间复杂度 | 最大操作次数估算 | 适用算法示例 |
|---|---|---|---|
| ≤ (10^2) | O(n³)、O(2ⁿ) | ≤ 1,000,000 | 暴力搜索、全排列枚举 |
| ≤ (10^4) | O(n²)、O(n² log n) | ≤ (10^8) | 冒泡排序、Floyd-Warshall |
| ≤ (10^6) | O(n log n)、O(n) | ≤ (10^7) | 快速排序、并查集 |
| ≤ (10^8) | O(n)、O(log n)、O(1) | ≤ (10^8) | 计数排序、哈希查找、二分法 |
| > (10^8) | O(log n)、O(1) | 必须严格优化 | 布隆过滤器、位图索引 |
二、不同规模下的算法选择策略
1. 小规模数据（n ≤ 1,000）
- 特点：无需过度优化，注重代码简洁性
- 适用算法：
- 排序：冒泡排序（O(n²)）
- 最短路径：Floyd-Warshall（O(n³)）
- 子集问题：暴力枚举所有组合（O(2ⁿ)）
2. 中等规模数据（n ≤ 100,000）
- 特点：需避免指数级复杂度，优先考虑多项式算法
- 适用算法：
- 排序：快速排序（O(n log n)）
- 图遍历：Dijkstra+堆优化（O(m log n)）
- 动态规划：背包问题（O(nW)）
3. 大规模数据（n ≤ 10⁷）
- 特点：线性时间复杂度是底线，需优化空间局部性
- 适用算法：
- 排序：归并排序（O(n log n)）
- 查找：哈希表（O(1)）
- 统计：前缀和（O(n)）
4. 超大规模数据（n > 10⁸）
- 特点：必须使用亚线性或常数级算法
- 适用技术：
- 近似算法：HyperLogLog统计基数
- 概率数据结构：布隆过滤器查存在
- 分布式处理：MapReduce分治