能否编写O(n)时间复杂度的T-SQL查询获取最大2个元素？ORDER BY复杂度疑问

一、能否编写O(n)时间复杂度的T-SQL查询获取最大的2个元素？ #

当然可以！你不需要依赖全表排序来实现这个需求，只需要遍历一次数据集，跟踪记录最大的两个值即可，这种方法的时间复杂度严格为O(n)。

举个具体的T-SQL示例，假设我们有一个名为YourTable的表，其中包含value列：

DECLARE @Max1 INT, @Max2 INT;

-- 初始化变量（如果表可能有负数，建议初始化为极小值，比如-2147483648）
SET @Max1 = NULL;
SET @Max2 = NULL;

SELECT 
    @Max2 = CASE 
        WHEN value IS NOT NULL THEN
            CASE
                WHEN @Max1 IS NULL THEN NULL -- 还没找到第一个最大值
                WHEN value > @Max1 THEN @Max1 -- 当前值比最大的还大，原来的最大值退居第二
                WHEN value > @Max2 OR @Max2 IS NULL THEN value -- 当前值比第二大的大，更新第二大
                ELSE @Max2 -- 无变化
            END
        ELSE @Max2
    END,
    @Max1 = CASE 
        WHEN value IS NOT NULL THEN
            CASE
                WHEN @Max1 IS NULL THEN value -- 第一个有效值作为最大值
                WHEN value > @Max1 THEN value -- 更新最大值
                ELSE @Max1 -- 无变化
            END
        ELSE @Max1
    END
FROM YourTable;

-- 输出结果
SELECT 
    最大值 = @Max1,
    第二大值 = @Max2;

这个查询只需要对表进行一次全扫描，每一行只做简单的条件判断和变量更新，完全没有排序操作，因此时间复杂度是O(n)。

另外，如果你的表在value列上有降序索引，那么使用SELECT TOP 2 value FROM YourTable ORDER BY value DESC的执行计划会直接从索引中读取前两条记录，此时时间复杂度甚至可以低至O(1)（或者说接近常数时间，因为索引的查找成本极低），这也是一种高效的O(n)级别的实现（严格来说是O(k)，k是你要取的元素数量）。

二、包含ORDER BY的查询是否始终至少具有O(n log n)的时间复杂度？ #

答案是否定的，并非所有带ORDER BY的查询都需要O(n log n)的时间。SQL Server的查询优化器会根据数据分布、索引情况等因素选择最优的执行计划，很多时候可以避免全表排序：

• 利用有序索引：如果ORDER BY的列上存在匹配顺序（升序/降序）的索引，优化器会直接扫描索引的有序数据，不需要额外排序，此时时间复杂度为O(n)（扫描整个索引）或者O(k)（取TOP k条记录）。
• 低基数列排序：如果排序列的不同值很少（比如只有几个枚举值），SQL Server可能会使用哈希分组或其他优化策略，排序的时间成本远低于O(n log n)。
• 小结果集排序：如果查询返回的结果集非常小（比如只取前10条），即使需要排序，实际的时间开销也可以忽略不计，理论复杂度也远低于O(n log n)。

只有当需要对无索引的大结果集进行全排序时，才会触发O(n log n)复杂度的排序操作（比如执行计划中出现Sort运算符）。

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