我如何阐明 O(n^3) 函数的时间复杂度？

Question

对于这样的伪代码算法：

Algorithm fn(A, S):
    Inputs: array A of n integers
            integer S

    for i from 0 up to n - 1:
        for j from i + 1 up to n - 1:
            for k from j + 1 up to n - 1:
                if A[i] + A[j] + A[k] == S:
                    return true

    return false

为什么它最坏情况的时间复杂度是O(n^3)。我是大 O 表示法的新手，我需要一些帮助来解释为什么这个函数的最坏情况是 O(n^3)。我推断它是 O(n^3)，因为它有三个 for 循环；但是，我也觉得这是一种肤浅的认识。

Answer 1

您所展示的是多项式时间算法的示例。你是对的，最坏的情况是来自三个嵌套 for 循环的

O(n^3)

。

此示例中最糟糕的情况是，直到最后一次可能的嵌套迭代才找到

A[i] + A[j] + A[k]

和

intger S

的值之间的匹配。相反，最好的情况是第一次就找到匹配。