为何O(n²logn)后缀数组实现比O(nlog²n)高效版表现更优？

我在学习后缀数组理论后，实现了两种构造算法验证理解，两种算法在小测试用例和大规模输入下均输出正确结果，但当输入规模为1000（由随机"abn"字符生成）时，理论上更高效的倍增版反而在时间与空间表现上不如朴素版，现排查实现层面的原因。

1. 朴素版后缀数组实现 #

生成输入字符串的所有后缀并按字典序排序，理论时间复杂度O(n²logn)，空间复杂度O(n²)：

def naive_suffix_array(text: str) -> list[int]:
    n = len(text)
    suffixes = [(text[i:], i) for i in range(n)]
    suffixes.sort()
    suffix_array = [index for _, index in suffixes]
    return suffix_array

2. 倍增法高效版实现 #

采用倍增技术，基于前k个字符排序后缀，k逐步倍增至≥n，理论时间复杂度O(nlog²n)，空间复杂度O(n)：

def efficient_suffix_array(text: str) -> list[int]:
    text = text + "$"  # 添加特殊字符到字符串末尾
    
    n = len(text)
    k = 1

    # 用字符的ASCII值初始化rank数组
    rank = [ord(c) for c in text]

    while k < n:
        # 基于前k个字符排序后缀（suffixes是索引列表）
        suffixes = sorted(
            range(n),
            key=lambda i: (rank[i], rank[(i + k) % n])
        )
        
        # 更新rank数组为新的排名值
        new_rank = [0] * n
        rank_value = 0  # 排名变化时递增
        prev_suffix = suffixes[0]  # 排名第一的后缀
        new_rank[prev_suffix] = rank_value  # 排名第一的后缀赋值为0

        for i in range(1, n):
            cur_suffix = suffixes[i]  
            if rank[cur_suffix] != rank[prev_suffix] or rank[(cur_suffix + k) % n] != rank[(prev_suffix + k) % n]:
                # 当前后缀与前一个后缀的前k或后k字符排名不同，更新排名值
                rank_value += 1
            new_rank[cur_suffix] = rank_value
            prev_suffix = cur_suffix
        
        if rank_value == n - 1:
            # 所有后缀已区分开，提前终止循环
            break

        rank = new_rank
        k *= 2

    return suffixes[1:]  # 第一个后缀总是$，无需返回

测试用例 #

输入规模为1000的随机字符串生成代码：

import random
text: str = "".join(random.choice("abn") for _ in range(1000))

性能异常的原因分析 #

1. Python内置排序的常数开销 #

倍增法每次迭代都调用sorted，虽然理论时间复杂度更优，但Python的sorted是Timsort实现，且本次排序的key是Python层面的lambda函数，每次排序都要执行多次(rank[i], rank[(i+k)%n])的计算，引入了额外的Python解释器开销。而朴素版的字符串排序依赖Python内置的高度优化的C级字符串比较，在n=1000的规模下，这种常数开销的差异超过了理论复杂度的优势。

2. 朴素版的实际空间开销远低于理论值 #

Python中字符串切片（text[i:]）不会复制整个子串，而是共享原字符串的底层字符数组，仅创建新的字符串对象记录起始位置和长度。因此朴素版的实际空间开销是O(n)级别，而非理论上的O(n²)，导致倍增法的空间优势无法体现，甚至因为维护rank、new_rank等多个数组，空间表现反而不如朴素版。

3. 小字符集场景的影响 #

测试用例仅使用"a""b""n"三个字符，朴素版的字符串比较往往只需对比前几个字符就能分出顺序，实际比较次数远低于理论的n²。而倍增法无论字符集大小，都需要执行logn次完整的数组排序，在这种场景下实际执行的操作次数反而更多。

优化方向 #

1. 替换为基数排序 #

将每次迭代的sorted替换为基数排序，利用排序键是二元组的特性，先按第二关键字排序，再按第一关键字排序。基数排序可以用更高效的底层实现（或借助Python的array模块优化），避免lambda函数的开销，同时将时间复杂度降到O(nlogn)。

2. 减少数组内存开销 #

复用rank数组，避免每次创建新的new_rank列表，例如使用两个数组交替更新，减少内存分配和复制的开销。

3. 优化排序键的计算 #

预先计算好每个索引对应的第二关键字值，避免在排序时重复计算rank[(i+k)%n]，减少函数调用和数组访问的次数。

内容的提问来源于stack exchange，提问作者FluidMechanics Potential Flows