算法时间复杂度咨询：嵌套循环下是n⁴还是n⁴logn？

根据你提供的伪代码，核心逻辑可还原为如下结构：

for i from 1 to n:
    for j from 1 to n:
        for k from 1 to n:
            S = 空集合
            for l from 1 to n:
                将A[l]插入S
            对S进行排序

复杂度拆解 #

• 外层三层i/j/k循环：每层迭代n次，总次数为n³。
• 内层l循环：每次执行n次集合插入操作，最坏情况下数组A无重复元素，插入后集合S的大小为n。
• 排序操作：对大小为n的集合排序，基于比较的排序算法时间复杂度为O(n logn)，这是无法省略的核心成本。

每次外层三层循环的迭代中，内层操作的总时间由排序主导，为O(n logn)。因此整个算法的时间复杂度为：
n³ * O(n logn) = O(n⁴ logn)

关于朋友结论的说明 #

朋友认为复杂度是O(n⁴)，大概率是忽略了排序的logn项——要么误以为排序是线性或常数时间操作，要么错误假设集合S的大小是固定常数。但时间复杂度分析默认取最坏情况，此时排序的O(n logn)成本必须计入，因此正确复杂度应为O(n⁴ logn)。

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