为何count2b函数时间复杂度呈平方级？嵌套循环复杂度分析

我们有三个功能完全一致的C++函数，输入的std::vector<int>是升序排列的，且满足lower < upper：

函数1：count1 #

预期时间复杂度：O(n log n)，因为每次循环都包含二分查找操作。

long long count1(std::vector<int> const& v, int lower, int upper) {
    long long count = 0;
    for (int i = 0; i < v.size(); ++i) {
        count += std::upper_bound(begin(v)+i, end(v), v[i] + upper)
                -std::lower_bound(begin(v)+i, end(v), v[i] + lower);
    }
    return count;
}

函数2：count2a #

预期时间复杂度：O(n)，因为指针l和r最多各自移动n次，整体循环次数是线性的。

long long count2a(std::vector<int> const& v, int lower, int upper) {
    long long count = 0;
    int n = v.size(), l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        while (l < n && v[l] - v[i] < lower) ++l;
        while (r < n && v[r] - v[i] <= upper) ++r;
        count += r - l;
    }
    return count;
}

函数3：count2b #

原本预期时间复杂度为O(n)且比count2a更快，但实际基准测试显示其时间复杂度为O(n²)。

long long count2b(std::vector<int> const& v, int lower, int upper) {
    long long count = 0;
    int n = v.size(), l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        while (l < n && v[l] - v[i] < lower) ++l;
        r = l; // 新增的一行
        while (r < n && v[r] - v[i] <= upper) ++r;
        count += r - l;
    }
    return count;
}

基准测试结果 #

测试显示三个函数的时间复杂度指数分别为1.1、0.9、2.0——也就是说count2b的运行时间随n增长呈平方级变化，这和预期不符。

核心原因 #

count2b的问题出在每次循环都将r重置为l，破坏了count2a中r的单调递增特性：

• 在count2a中，r是单调递增的：因为输入数组升序，v[i]随i增大而增大，v[i]+upper也随之增大。上一轮循环中找到的r位置，必然满足v[r] <= v[i-1]+upper <= v[i]+upper，因此后续循环中r不需要回退，只需要从当前位置继续向后遍历，整个过程中r最多移动n次。
• 但在count2b中，每次循环都把r重置为当前的l。当upper取值较大时，v[r]-v[i] <= upper的条件几乎对所有r >= l都成立，此时每个i对应的r都需要从l遍历到数组末尾。由于l是从0逐步递增到n的，总遍历次数会变成n + (n-1) + ... + 1 = O(n²)，直接导致平方级的时间复杂度。

比如极端情况：upper远大于数组中最大元素与最小元素的差值，此时对于每个i，r都会从l走到数组末尾，总操作次数就是等差数列求和，量级为n²。

完整可运行测试代码 #

#include <iostream>
#include <fstream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>
#include <cmath>
using namespace std::chrono;

long long count1(std::vector<int> const& v, int lower, int upper) {
    long long count = 0;
    for (int i = 0; i < v.size(); ++i) {
        count += std::upper_bound(begin(v)+i, end(v), v[i] + upper)
                -std::lower_bound(begin(v)+i, end(v), v[i] + lower);
    }
    return count;
}
long long count2a(std::vector<int> const& v, int lower, int upper) {
    long long count = 0;
    int n = v.size(), l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        while (l < n && v[l] - v[i] < lower) ++l;
        while (r < n && v[r] - v[i] <= upper) ++r;
        count += r - l;
    }
    return count;
}
long long count2b(std::vector<int> const& v, int lower, int upper) {
    long long count = 0;
    int n = v.size(), l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        while (l < n && v[l] - v[i] < lower) ++l;
        r = l;
        while (r < n && v[r] - v[i] <= upper) ++r;
        count += r - l;
    }
    return count;
}

void benchmark(int r, std::ostream& os, auto&& func, auto&&... args) {
    long long test = 0;
    std::vector<long long> times;
    for (int i = 0; i < r; ++i) {
        auto t0 = high_resolution_clock::now();
        test += func(std::forward<decltype(args)>(args)...);
        auto t1 = high_resolution_clock::now();
        times.push_back(duration_cast<nanoseconds>(t1 - t0).count());
    }
    double mean = 0, sd = 0;
    for (auto& d : times) {
        mean += d;
    }
    mean /= times.size();
    for (auto& d : times) {
        sd += pow((d - mean), 2);
    }
    sd = sqrt(sd / times.size());

    os << mean << " " << sd << " ";
    std::cout << test << std::endl;
}

int main() {
    std::mt19937 reng;
    std::uniform_int_distribution<int> d(0, 1e8);
    std::ofstream file("bench.txt");
    for (int n = 100; n < 1e5; n *= 1.1) {
        int r = 2;

        std::cout << "n = " << n << std::endl;

        std::vector<int> v(n);
        for (auto& a : v) a = d(reng);
        std::sort(begin(v), end(v));
        int lower = d(reng), upper = lower + d(reng);

        file << n << " ";
        benchmark(r, file, &count1, v, lower, upper);
        file << std::endl;
        file << n << " ";
        benchmark(r, file, &count2a, v, lower, upper);
        file << std::endl;
        file << n << " ";
        benchmark(r, file, &count2b, v, lower, upper);
        file << std::endl;
    }
    file.close();
    return 0;
}

（注：原代码中的void main()不符合C++标准，已修正为int main()并添加return 0;，同时补充了缺失的<algorithm>和<cmath>头文件）

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