为何线性搜索的耗时未随数组规模呈线性增长？

我尝试用C++实现二分搜索与线性搜索的基准测试，预期线性搜索（Naive方法）耗时随数组规模线性增长，但实际生成的图表不符合预期，即使关闭编译器优化（g++ -O0）也没有改善。

C++基准测试实现代码 #

#include <chrono>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size() - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (target > nums[mid]) {
                low = mid+1;
            } else if (target < nums[mid]) {
                high = mid-1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    int naiveSearch(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == target) {
                return i;
            }
        }

        return -1;
    }
};

int main() {
    Solution sol;
    for(int n = 1000; n <= 10000000; n += 10000) {
        // Random target, always gonna be in the array
        int target = rand()%n+1;

        vector<int> nums(n);
        iota(nums.begin(), nums.end(), 1);

        auto start = std::chrono::high_resolution_clock::now();
        sol.search(nums, target);
        auto stop = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
        cout << n << "," << duration.count() << ",Binary" << endl;

        start = std::chrono::high_resolution_clock::now();
        sol.naiveSearch(nums, target);
        stop = std::chrono::high_resolution_clock::now();
        duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
        cout << n << "," << duration.count() << ",Naive" << endl;
    }

    return 0;
}

Python绘图代码 #

import matplotlib.pyplot as plt
import pandas as pd

data = pd.read_csv('data.csv', names=['Size', 'Time', 'Method'])

binary_data = data[data['Method'] == 'Binary']
naive_data = data[data['Method'] == 'Naive']

plt.plot(binary_data['Size'], binary_data['Time'], label='Binary')
plt.plot(naive_data['Size'], naive_data['Time'], label='Naive')

plt.xlabel('Input size')
plt.ylabel('Time (microseconds)')
plt.legend()

plt.show()

问题原因分析 #

• 单次测量误差过大：每个数组规模仅执行一次搜索，单次运行时间极短，计时精度不足导致数据波动剧烈，无法体现真实时间复杂度。
• 随机目标位置不稳定：rand()%n+1生成的目标在数组中的位置随机，单次运行的目标可能偏前或偏后，直接导致线性搜索耗时差异大。
• CPU缓存预取优化：数组是连续内存的有序序列，CPU的缓存预取机制大幅提升了线性搜索的效率，小数据量下甚至抵消了时间复杂度的差异。
• 随机种子未固定：每次运行程序的默认随机种子不同，导致不同次运行的目标位置完全不一致，数据缺乏可比性。

改进方案 #

• 固定随机种子：在main函数开头添加std::srand(42);，保证每次运行生成的目标位置一致。
• 多次重复取平均：对每个数组规模，重复执行搜索函数（如1000次），累加总时间后计算平均值，减少单次测量的误差。
• 隔离数组生成时间：将数组生成代码放在计时区域之外，避免初始化时间干扰搜索耗时的测量。
• 使用随机数组：生成无序的随机数组，避免CPU预取优化对线性搜索的特殊加持，更贴近真实场景。

内容的提问来源于stack exchange，提问作者JasonFrom2008