如何找到以下代码片段的时间复杂度？

Question

我被要求解决一个问题，我从整数数组 A 中找到降序排序的三元组，其中 0<=i A[j] > A[k]。我的蛮力解决方案是 O(n^3)，优化后，我想出了以下代码，我正在努力寻找它的时间复杂度：

def getTriplet2(array):
    i, j, k, n = 0, 1, 2, len(array)
    while i < j < k < n:
        if array[i] > array[j] > array[k]:
            return array[i], array[j], array[k]
        elif array[k] > array[j]:
            if i == n - 3:
                break
            if j == n - 2:
                i += 1
                j = i + 1
                k = j + 1
            if k == n - 1:
                j += 1
                k = j + 1
            else:
                k += 1
        else:
            i += 1
            j += 1
            k += 1

Answer 1

本质上，在最坏的情况下，您正在访问所有排序的索引三元组，这将是一个单调递增的数组（

i < j < k => A[i] < A[j] < A[k]

普遍成立）。

要看到这一点，请注意对于这种输入，条件的分支

elif array[k] > array[j]:

将在每次迭代中执行。该分支执行于

O(1)

.

索引三元组的个数从小到大就是由不同数字组成的索引三元组的个数，即

O(n \over 3) = O(n^3)

.

渐近优化的解决方案并不比蛮力运行得更快。