实验 1: 渐进分析和排序算法

这份实验围绕渐进分析、分治与排序展开，共有五个 Task。代码附件采用 C++17，正文展示与附件一致的核心实现。

代码与实验记录

编辑版代码已完成编译、边界与随机差分检查，并通过 AddressSanitizer / UndefinedBehaviorSanitizer 检查。Task 4、Task 5 的五张图及其观察保留为原实验记录；缺少的原始数据和实验环境尚不能补齐，本轮正确性测试没有生成新的性能结果。

Task 1 #

以下令 $n$ 为正整数。渐进界要求找到固定常数和阈值，使相应不等式对阈值之后的所有 $n$ 成立。

• (1) 使用 $O,\Omega$ 和 $\Theta$ 的定义，证明下面各式。
• a) $2\sqrt n+6=O(\sqrt n)$。

证明

取 $C=8$、$n_0=1$。对所有 $n\ge n_0$，有 $\sqrt n\ge1$，从而

$$0\le2\sqrt n+6\le8\sqrt n=C\sqrt n.$$

因此 $2\sqrt n+6=O(\sqrt n)$。

• b) $n^2=\Omega(n)$。

证明

取 $c=1$、$n_0=1$。对所有 $n\ge n_0$，都有 $n^2\ge cn\ge0$，故 $n^2=\Omega(n)$。

• c) $\log_2 n=\Theta(\ln n)$。

证明

取 $c_1=c_2=1/\ln2$、$n_0=2$。换底公式给出：对所有 $n\ge n_0$，

$$0<c_1\ln n=\log_2 n=c_2\ln n.$$

上下界同时成立，故 $\log_2 n=\Theta(\ln n)$。

• d) $4^n\notin O(2^n)$。

证明

需要证明：对任意 $C>0$ 和任意正整数阈值 $n_0$，总能找到 $n\ge n_0$ 使 $4^n>C2^n$。

取

$$n=\max\{n_0,1,\lfloor\log_2 C\rfloor+1\}.$$

则 $n\ge n_0$ 且 $n>\log_2 C$，所以

$$\frac{4^n}{2^n}=2^n>C.$$

这否定了 Big-O 定义中“存在一组 $C,n_0$，使所有更大的 $n$ 满足上界”的断言。

• (2) 使用数学归纳法证明 $T(n)=O(n^2)$，其中

$$T(n)=\begin{cases} T(n-1)+2n,&n>1,\\ 3,&n=1. \end{cases}$$

证明

先固定 $C=3$，证明对每个正整数 $n$ 都有 $T(n)\le3n^2$。

基例为 $T(1)=3\le3\cdot1^2$。假设某个 $k\ge1$ 满足 $T(k)\le3k^2$，则

$$T(k+1)\le3k^2+2k+2\le3(k+1)^2,$$

最后一步的右式减左式为 $4k+1>0$。归纳完成，取 $n_0=1$ 即得结论。求和还可核对精确式 $T(n)=n(n+1)+1$；它与基例和递推式均一致。

Task 2 #

算法设计 #

题目为洛谷 P7883：平面最近点对（加强加强版）。题面规定 $2\le n\le4\times10^5$、整数坐标位于 $[-10^7,10^7]$，没有重合点，输出最近距离的平方。

将点按 $(x,y)$ 字典序排列为 $p_0,\ldots,p_{n-1}$。小区间直接枚举；其余取 $m=\lfloor n/2\rfloor$，分成

$$A_1=\{p_i:0\le i<m\},\qquad A_2=\{p_i:m\le i<n\}.$$

分界线取 $x=x_m$。递归求出两侧内部的最近距离 $h_1,h_2$，令 $h=\min(h_1,h_2)$。横坐标相等的点仍按数组下标归属子集，不能把“左子集”简单等同于 $x<x_m$。

能使答案小于 $h$ 的跨侧点对，两个点都必须位于条带

$$B=\{p\in A_1\cup A_2:|x(p)-x_m|<h\}.$$

按 $(y,x)$ 排列 $B$ 为 $q_0,\ldots,q_{s-1}$，令 $y_i=y(q_i)$。扫描到 $q_i$ 时只检查它的已扫描前驱：

$$C(q_i)=\{q_j:0\le j<i,\quad y_i-h<y_j\le y_i\}.$$

这里集合元素、下标和纵坐标指向同一个 $q_j$，并由 $j<i$ 明确排除自身。即使纵坐标相等，一对点也只检查一次。逐一比较 $q_i$ 与 $C(q_i)$ 中的点，即可更新答案。

复杂度分析 #

若每层独立对条带排序，会得到 $O(n\log^2 n)$ 的算法；题面允许这一目标，但这里用归并保持每个返回区间的 $y$ 有序性，将每层合并降为线性时间。递归前先保存分界横坐标，避免子调用改变数组顺序后再取分界点。

当 $h>0$ 时，$C(q_i)$ 连同 $q_i$ 落在一个宽 $2h$、高 $h$ 的矩形中。分别按两个递归子集计数：每个子集在相应宽 $h$ 的半区内，两点距离至少为 $h$。把每半区划分为四个边长 $h/2$ 的小格，每格对该子集至多容纳一点，否则距离最多为 $h/\sqrt2<h$。分界线上的点也按其原子集归属计数，因此总数至多为 $8$，除去 $q_i$ 后至多比较 $7$ 个前驱。

实现中答案会收紧，但收紧后的候选仍包含在初始 $h$ 的条带和纵向窗口中，因此这一常数界仍成立。若已经得到零距离，可在完成该区间的归并后直接返回零。

于是

$$T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+O(n)=O(n\log n).$$

辅助数组和输入副本占用 $O(n)$ 空间。实现全程使用平方距离：best 对应 $h^2$，横向筛选为 $(x-x_m)^2<\texttt{best}$，纵向停止条件为 $(y_i-y_j)^2\ge\texttt{best}$，不需要开方。

代码实现 #

以下核心函数来自算法头文件。closest_squared 不修改调用者的点集；零点或单点返回 std::nullopt，重合点返回零，超过点数或坐标范围则抛出 std::invalid_argument。后两项中的重合点处理是编辑版额外约定，不是原题要求。

先转为 int64_t 再做减法。在规定坐标范围内，两轴差的绝对值至多为 $2\times10^7$，距离平方至多为 $8\times10^{14}$，不会溢出 64 位有符号整数。内部区间函数只由通过范围检查的入口调用。

struct Point {
    std::int32_t x;
    std::int32_t y;
};

inline std::int64_t squared_distance(Point a, Point b) {
    const auto dx = std::int64_t(a.x) - std::int64_t(b.x);
    const auto dy = std::int64_t(a.y) - std::int64_t(b.y);
    return dx * dx + dy * dy;
}

inline bool by_y(Point a, Point b) {
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}

// Entry: x order on [l,r). Return: y order on the same interval.
inline std::int64_t closest_range(std::vector<Point>& a,
                                 std::vector<Point>& scratch,
                                 std::size_t l, std::size_t r) {
    auto best = std::numeric_limits<std::int64_t>::max();
    if (r - l <= 3) {
        for (auto i = l; i < r; ++i)
            for (auto j = i + 1; j < r; ++j)
                best = std::min(best, squared_distance(a[i], a[j]));
        std::sort(a.begin() + l, a.begin() + r, by_y);
        return best;
    }
    const auto mid = l + (r - l) / 2;
    const auto px = a[mid].x;
    const auto left = closest_range(a, scratch, l, mid);
    const auto right = closest_range(a, scratch, mid, r);
    best = std::min(left, right);
    std::merge(a.begin() + l, a.begin() + mid,
               a.begin() + mid, a.begin() + r,
               scratch.begin() + l, by_y);
    std::copy(scratch.begin() + l, scratch.begin() + r, a.begin() + l);
    if (best == 0) return 0;

    std::size_t count = 0;
    for (auto i = l; i < r; ++i) {
        const auto dx = std::int64_t(a[i].x) - std::int64_t(px);
        if (dx * dx >= best) continue;
        for (auto j = count; j > 0; --j) {
            const auto dy = std::int64_t(a[i].y) - std::int64_t(scratch[j - 1].y);
            if (dy * dy >= best) break;
            best = std::min(best, squared_distance(a[i], scratch[j - 1]));
        }
        scratch[count++] = a[i];
    }
    return best;
}

inline std::optional<std::int64_t> closest_squared(std::vector<Point> points) {
    if (points.size() > 400000) throw std::invalid_argument("too many points");
    for (const auto p : points) {
        if (p.x < -10000000 || p.x > 10000000 ||
            p.y < -10000000 || p.y > 10000000)
            throw std::invalid_argument("coordinate outside [-10^7,10^7]");
    }
    if (points.size() < 2) return std::nullopt;
    std::sort(points.begin(), points.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    std::vector<Point> scratch(points.size());
    return closest_range(points, scratch, 0, points.size());
}

标准输入输出程序与上述头文件放在同一目录编译。它严格要求至少两个点，输入错误时向标准错误输出原因并以非零状态退出。

#include "experiment1-algorithms.hpp"
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::int64_t n = 0;
    if (!(std::cin >> n) || n < 2 || n > 400000) {
        std::cerr << "expected 2 <= n <= 400000\n";
        return 1;
    }
    std::vector<experiment1::Point> points;
    points.reserve(static_cast<std::size_t>(n));
    for (std::int64_t i = 0; i < n; ++i) {
        std::int64_t x = 0, y = 0;
        if (!(std::cin >> x >> y) || x < -10000000 || x > 10000000 ||
            y < -10000000 || y > 10000000) {
            std::cerr << "invalid or missing coordinate\n";
            return 1;
        }
        points.push_back({static_cast<std::int32_t>(x), static_cast<std::int32_t>(y)});
    }
    std::cout << *experiment1::closest_squared(std::move(points)) << '\n';
}

例如输入两个点 (0,0)、(3,4)，输出为 25，不是 5。原实验记载曾通过 P7883；编辑版已经通过文末的独立测试，但没有重新向评测站提交，不据此宣称再次通过其时限。

Task 3 #

性能记录使用了 50 组不同规模的随机、正序和逆序数据。下列是整理后的排序实现，它们都接收整个 std::vector<int> 并原地升序排序；空数组和单元素数组保持不变。递归辅助函数使用合法半开区间 [l,r)，不把未校验的任意端点作为公共接口。

这些函数同属 experiment1 命名空间，完整头文件已包含所需标准库。这里的实现用于学习和正确性复现，不能在缺少原实验驱动时替代产生原图的代码版本。

插入排序 #

扫描已排序前缀，遇到不大于当前值的元素即停止。与始终遍历整个前缀的写法相比，这个停止条件使正序输入只需线性次检查。

inline void Insertion(std::vector<int>& num) {
    for (std::size_t i = 1; i < num.size(); ++i) {
        const int value = num[i];
        auto j = i;
        while (j > 0 && value < num[j - 1]) {
            num[j] = num[j - 1];
            --j;
        }
        num[j] = value;
    }
}

选择排序 #

每轮确定未排序后缀的最小值，放入当前位置。

inline void Selection(std::vector<int>& num) {
    for (std::size_t i = 0; i + 1 < num.size(); ++i) {
        auto pos = i;
        for (auto j = i + 1; j < num.size(); ++j)
            if (num[j] < num[pos]) pos = j;
        std::swap(num[i], num[pos]);
    }
}

希尔排序 #

三组增量仍从 $1$ 开始，分别采用 $2h$、$2h+1$ 和 $3h+1$：

实现	递增生成的增量示例
Shell_1	1、2、4、8、16
Shell_2	1、3、7、15、31
Shell_3	1、4、13、40、121

第三式与原来的 ((H[p]<<1|1)*3-1)/2 在整数不溢出时等价，第二式同理等于 2*h+1。编辑版直接使用这些递推、动态容器和乘加前的上界检查，不再依赖固定的 H[30] 或有符号左移。实际按增量逆序进行插入排序；最后一趟增量为 $1$，保证整体有序。

inline std::vector<std::size_t> shell_gaps(std::size_t n, int mode) {
    if (mode < 1 || mode > 3) throw std::invalid_argument("invalid Shell mode");
    const std::size_t multiplier = mode == 3 ? 3 : 2;
    const std::size_t add = mode == 1 ? 0 : 1;
    std::vector<std::size_t> gaps;
    for (std::size_t h = 1; h < n;) {
        gaps.push_back(h);
        if (h > (std::numeric_limits<std::size_t>::max() - add) / multiplier)
            break;
        h = multiplier * h + add;
    }
    return gaps;
}

inline void Shell(std::vector<int>& num, int mode) {
    const auto gaps = shell_gaps(num.size(), mode);
    for (auto it = gaps.rbegin(); it != gaps.rend(); ++it) {
        const auto h = *it;
        for (auto i = h; i < num.size(); ++i) {
            const int value = num[i];
            auto j = i;
            while (j >= h && value < num[j - h]) {
                num[j] = num[j - h];
                j -= h;
            }
            num[j] = value;
        }
    }
}

inline void Shell_1(std::vector<int>& num) { Shell(num, 1); }
inline void Shell_2(std::vector<int>& num) { Shell(num, 2); }
inline void Shell_3(std::vector<int>& num) { Shell(num, 3); }

快速排序 #

每次从当前非空区间均匀抽取一个轴值，分区后左侧严格小于轴值、右侧大于等于轴值。默认种子为 20260911，调用时可显式指定；相同工具链下可以重放随机过程，不承诺不同标准库实现产生完全相同的轴值序列。

只对较短一侧递归，较长一侧在当前栈帧内继续处理，避免退化划分耗尽调用栈。返回值记录概念上的分割树最大深度：空数组为零，非空根节点为一；它不是实际调用栈深度，也不冒充旧图的统计口径。全相等数组仍可能产生二次运行时间，这里没有把随机选轴当成消除所有退化的保证。

inline std::size_t partition(std::vector<int>& num, std::size_t l,
                             std::size_t r, std::mt19937& rng) {
    std::uniform_int_distribution<std::size_t> choose(l, r - 1);
    std::swap(num[choose(rng)], num[r - 1]);
    const int pivot = num[r - 1];
    auto boundary = l;
    for (auto j = l; j + 1 < r; ++j)
        if (num[j] < pivot) std::swap(num[boundary++], num[j]);
    std::swap(num[boundary], num[r - 1]);
    return boundary;
}

inline void quick_range(std::vector<int>& num, std::size_t l, std::size_t r,
                        std::size_t depth, std::size_t& max_depth,
                        std::mt19937& rng) {
    while (l < r) {
        max_depth = std::max(max_depth, depth);
        if (r - l == 1) return;
        const auto p = partition(num, l, r, rng);
        // Recurse only into the smaller side; the larger side uses this frame.
        if (p - l < r - (p + 1)) {
            quick_range(num, l, p, depth + 1, max_depth, rng);
            l = p + 1;
        } else {
            quick_range(num, p + 1, r, depth + 1, max_depth, rng);
            r = p;
        }
        ++depth;
    }
}

inline std::size_t Quicksort(std::vector<int>& num,
                             std::uint32_t seed = 20260911U) {
    std::mt19937 rng(seed);
    std::size_t max_depth = 0;
    quick_range(num, 0, num.size(), 1, max_depth, rng);
    return max_depth;
}

归并排序 #

空区间和单元素区间直接返回；一次申请辅助数组，合并时相等元素先取左侧，保持稳定性。

inline void merge_range(std::vector<int>& num, std::vector<int>& scratch,
                        std::size_t l, std::size_t r) {
    if (r - l < 2) return;
    const auto mid = l + (r - l) / 2;
    merge_range(num, scratch, l, mid);
    merge_range(num, scratch, mid, r);
    auto i = l;
    auto j = mid;
    auto k = l;
    while (i < mid && j < r)
        scratch[k++] = num[i] <= num[j] ? num[i++] : num[j++];
    while (i < mid) scratch[k++] = num[i++];
    while (j < r) scratch[k++] = num[j++];
    std::copy(scratch.begin() + l, scratch.begin() + r, num.begin() + l);
}

inline void Mergesort(std::vector<int>& num) {
    if (num.size() < 2) return;
    std::vector<int> scratch(num.size());
    merge_range(num, scratch, 0, num.size());
}

Task 4 #

以下为各排序算法实际运行时间测试, 同一组数据采取运行 $20$ 次所需时间的平均值.

考虑到选择和插入排序的效率过慢, 故对其余算法进行了更大数据集的测试和单独的图表绘制. 以此更清晰的表示其余算法的效率差异.

随机数据 #

正序数据 #

逆序数据 #

总结 #

复杂度需区分最坏与期望情况：插入、选择排序的最坏时间为 $O(n^2)$，归并排序为 $O(n\log n)$；在元素互异且独立均匀选轴的模型中，随机快排的期望时间为 $O(n\log n)$，最坏仍为 $O(n^2)$。在所列实验图中，插入和选择排序的用时明显高于其余算法。

而对于希尔, 快排, 归并和 C++ stl 中的 sort 函数. Shell_1 在小数据与其他算法时间差距不大, 但当数据规模进一步扩大后, 用时增长速度明显大于其余算法. 而 Shell_2 在大数据规模下也有较差的表现.

而快排和归并, 则一直用时接近, 只有细微差别. C++ stl 中的 sort 函数表现出了较优的性能.

对于不同的数据性质选择, 快排, 归并和希尔用时变化不大.

而插入排序, 如果是从后往前寻找插入位置时, 当数据为正序理论复杂度为 $\t O(n)$, 实际运行效率也很高.

这些比较均是本次记录中的观察，不是跨硬件、编译器或实现版本的普遍结论。图中的 TEST_NUM 与输入规模对应表、随机种子、优化参数、硬件、计时区间、预热方式和逐次原始数值尚未找到，因此暂时不能独立复现这些性能图，也不能从中推算方差或置信区间。

Task 5 #

快排层数 #

记录覆盖 $2^8\sim2^{19}$ 的 12 组规模，图中深度呈现接近对数参考曲线的增长趋势。但原记录没有说明每点是单次值、最大值还是多次平均，有限样本也不能独自建立渐进结论。

“轴值秩的期望在中间”不等于每次都会均匀分割，不能直接推出期望树高；这一结论需要对随机分割树另作分析。最坏分割可使概念深度达到 $n$，编辑版的全相等测试也覆盖了这种情况。代码返回的逻辑深度与真实调用栈深度已明确区分，不能用新的计数器反推原图。

快排优化 #

通过设定阈值分别为 $50$ 和 $5$，在 $2^8\sim2^{21}$ 这些数据中，原记录观察到优化过的两份算法略优于未优化版本，幅度不大；阈值 $50$ 相比 $5$ 快了几毫秒，区别也不大。

这只是图中保留的观察。两份阈值实现、切换策略、基线和计时数据尚未找到，无法确认差异是否稳定，也不能据此断言算法复杂度已经改变或未改变。本页没有编造对应实现来充当原实验代码。

螺丝螺母匹配问题 #

同类零件不能互相比较，允许的唯一比较是螺母与螺丝之间的三向比较。考虑选取一个轴值螺母，先分割螺丝；找到它唯一匹配的螺丝后，再用该螺丝分割螺母。然后在两侧继续执行同样的过程。

编辑版契约 #

原实验没有附完整题面与可编译驱动。以下采用明确的、可检验的契约，不把它当成已经恢复的原题规格：

• nuts 与 bolts 数量相同；允许同时为空。
• 两边具有相同的一组尺寸，各尺寸在每边恰好出现一次，即匹配唯一。
• 比较器只能调用 compare(nut, bolt)，返回负数、零、正数分别表示螺母较小、匹配、较大；结果须确定且与同一个尺寸全序一致。
• 零件可以复制和交换；算法本身不读取其尺寸字段，不比较两个螺母或两个螺丝。
• 成功后相同下标两件匹配，两个数组按尺寸升序排列。不同长度、缺配、重复尺寸或分区不一致抛出 std::invalid_argument；报错时数组可能已被重排，不提供原序不变保证。
• 对不满足一致性要求的任意比较器不作正确性承诺；不把比较器错误伪装成尺寸数据错误。

分区不变量与正确性 #

cross_partition 始终把 [l,low) 保持为小于轴值、[low,i) 为等于轴值、[i,high) 为待处理、[high,r) 为大于轴值。每步缩小待处理区间，因此能够终止并返回等值带。分割螺丝时反转跨类比较的符号，分割螺母时保持原符号。

按唯一匹配契约，两个等值带都应恰好包含一件。由于两边尺寸集合相同，小于轴值的数量相等，轴值最终下标也相同。轴值位置已经匹配，左右子区间仍分别具有相同、互异的尺寸集合；对区间长度归纳可得全部匹配。单件区间直接验证跨类相等，空区间不进行比较。

每层双分区为线性成本。均匀随机选取轴值时，对合法互异尺寸数据，期望时间与随机快排一样为 $O(n\log n)$；极端划分仍为 $O(n^2)$。只递归较短的一侧，使实际辅助调用栈为 $O(\log n)$，不依赖平均情况来避免线性深度的调用栈。

struct EqualBand { std::size_t begin, end; };

template<class Item, class RelativeOrder>
EqualBand cross_partition(std::vector<Item>& a, std::size_t l, std::size_t r,
                          RelativeOrder order) {
    auto low = l;
    auto i = l;
    auto high = r;
    while (i < high) {
        const int sign = order(a[i]);
        if (sign < 0) std::swap(a[low++], a[i++]);
        else if (sign > 0) std::swap(a[i], a[--high]);
        else ++i;
    }
    return {low, high};
}

template<class Nut, class Bolt, class Compare>
void match_range(std::vector<Nut>& nuts, std::vector<Bolt>& bolts,
                 std::size_t l, std::size_t r, Compare& compare,
                 std::mt19937& rng) {
    while (l < r) {
        if (r - l == 1) {
            if (compare(nuts[l], bolts[l]) != 0)
                throw std::invalid_argument("unmatched singleton");
            return;
        }
        std::uniform_int_distribution<std::size_t> choose(l, r - 1);
        const Nut pivot_nut = nuts[choose(rng)];
        const auto b = cross_partition(bolts, l, r, [&](const Bolt& bolt) {
            const int sign = compare(pivot_nut, bolt);
            return sign > 0 ? -1 : sign < 0 ? 1 : 0;
        });
        if (b.end - b.begin != 1)
            throw std::invalid_argument("missing or duplicate matching bolt");
        const Bolt pivot_bolt = bolts[b.begin];
        const auto n = cross_partition(nuts, l, r, [&](const Nut& nut) {
            return compare(nut, pivot_bolt);
        });
        if (n.end - n.begin != 1 || n.begin != b.begin)
            throw std::invalid_argument("duplicate nut or unequal size sets");
        const auto p = n.begin;
        if (p - l < r - (p + 1)) {
            match_range(nuts, bolts, l, p, compare, rng);
            l = p + 1;
        } else {
            match_range(nuts, bolts, p + 1, r, compare, rng);
            r = p;
        }
    }
}

template<class Nut, class Bolt, class Compare>
void MatchNutsBolts(std::vector<Nut>& nuts, std::vector<Bolt>& bolts,
                   Compare compare, std::uint32_t seed = 20260911U) {
    if (nuts.size() != bolts.size())
        throw std::invalid_argument("different counts");
    std::mt19937 rng(seed);
    match_range(nuts, bolts, 0, nuts.size(), compare, rng);
}

代码附件与验证 #

• 算法头文件：最近点对、七种排序和跨类匹配实现。
• 最近点对完整入口：标准输入输出及输入检查。
• 独立测试程序：穷举、小规模随机差分、边界与非法输入检查。
• 编译及契约说明。

将附件放在同一目录后，可以运行：

g++ -std=c++17 -O2 -Wall -Wextra -Wpedantic -Werror experiment1-tests.cpp -o experiment1-tests
./experiment1-tests
g++ -std=c++17 -O2 experiment1-closest-pair.cpp -o experiment1-closest-pair

2026-09-11 的编辑版在 Windows / GCC 14.2 与 Linux / GCC 13.3 下通过编译及同一组 202,982 次断言检查：4,296 组排序输入、2,018 组最近点对输入，以及 16,841 组匹配输入（其中 770 组非法输入被拒绝）。最近点对还覆盖 400,000 点上界，匹配测试用不提供同类比较运算符的类型实例化算法；标准输入输出入口另测了 11 组有效或无效输入。

Linux 检查实际启用了 ASan、UBSan 和标准库断言，未报告相应错误。测试记录证明这些用例下的结果与边界行为，不替代上述一般性证明，也不代表恢复了原实验的性能数据或验证了未知的题面要求。