如何分析这段寻找降序三元组的Python代码的时间复杂度？

首先明确这段代码的执行逻辑：

• 初始化三个指针i,j,k分别从0、1、2开始遍历数组
• 循环中根据当前三个元素的关系，分三种情况调整指针：
  1. 找到A[i]>A[j]>A[k]的三元组，直接返回结果
  2. 若A[k]>A[j]，则尝试右移k；若k到了数组末尾则右移j并重置k；若j也到了末尾则右移i并重置j,k；当i到达n-3时终止循环
  3. 其他情况（即A[j]>=A[k]但A[i]<=A[j]），将三个指针整体右移一位

最坏情况时间复杂度：O(n³) #

当数组是严格递增时，会触发最坏情况：
此时每次都会进入A[k]>A[j]的分支，k会从当前位置一直遍历到数组末尾，之后右移j并重置k，直到j到达末尾后再右移i，重复整个过程。

我们可以计算循环执行的总次数：
对于每个i（从0到n-3），j会从i+1遍历到n-2；对于每个j，k会从j+1遍历到n-1。总循环次数等价于遍历所有可能的三元组(i,j,k)的数量，即组合数C(n,3) = n(n-1)(n-2)/6，这属于**O(n³)**级别的时间复杂度，和暴力解法的时间复杂度一致。

为什么看起来像优化了？ #

只有当数组中存在符合条件的三元组且出现位置较早时，代码能提前返回，此时实际运行时间会比暴力法快。但从算法的最坏时间复杂度来看，它并没有真正优化，本质上还是在遍历大量三元组。

真正的优化思路（可选） #

如果要将时间复杂度降到O(n²)，可以固定中间元素j，然后在j左侧找比A[j]大的元素，右侧找比A[j]小的元素；或者进一步优化到O(n)时间：维护两个数组，分别记录每个位置左侧的最大值和右侧的最小值，然后遍历每个j，检查是否存在左侧最大值>A[j]且右侧最小值<A[j]。

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