如何阐述O(n³)函数的时间复杂度？解析三重循环算法复杂度

1. 如何清晰阐述O(n³)的时间复杂度 #

O(n³)属于多项式时间复杂度，核心是描述算法的运行时间（或执行的操作数）与输入规模n的增长关系：

• 当输入规模n增大时，算法所需的操作数会以n的三次方速度增长。比如n从100翻倍到200，操作数会从约100万增长到约800万（即2³倍）。
• 这类算法的效率会随输入规模扩大快速下降，仅适合处理小规模数据。
• 从渐近分析角度看，O(n³)表示当n趋近于无穷大时，算法的运行时间被某个与n³成正比的函数约束。

2. 该伪代码最坏情况时间复杂度为O(n³)的深入解释 #

你说的三重循环是直观感受，但本质要从循环执行的总操作数来拆解：

首先看算法逻辑：它要找数组中是否存在下标满足i<j<k的三个元素，其和等于S。最坏情况是数组中不存在这样的三元组，此时算法必须跑完所有循环，执行完所有判断操作。

我们计算循环的总执行次数：
这等价于从n个元素中选3个不同元素的组合数，数学上记为C(n,3)，计算公式为：

C(n,3) = n*(n-1)*(n-2)/6 = (n³ - 3n² + 2n)/6

当n足够大时，低次项（-3n²、2n）和常数系数（1/6）对整体增长趋势的影响可以忽略——渐近分析只关注最高次项的阶数。因此这个组合数的渐近复杂度就是O(n³)。

换句话说，最坏情况下，算法核心判断操作的执行次数与n³同阶，所以它的最坏情况时间复杂度为O(n³)。

附翻译后的伪代码：

算法 fn(A, S):
    输入：包含n个整数的数组A
          整数S

    从i=0到n-1遍历：
        从j=i+1到n-1遍历：
            从k=j+1到n-1遍历：
                如果A[i] + A[j] + A[k] == S：
                    返回true

    返回false

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