著名迭代任务复杂度：数组下一个更大元素暴力双循环平均复杂度

先快速回顾下问题：给定整数数组，为每个元素找到它之后第一个更大的元素，找不到就返回-1。比如输入7 2 4 6 16，正确输出应该是16,4,6,-1,-1（你给的示例漏了最后一个元素的-1，不过不影响核心问题~）。

朴素双重循环的逻辑非常直白：

• 逐个遍历数组里的每个元素arr[i]
• 从i+1的位置开始往后扫，直到找到第一个比arr[i]大的元素，或者扫到数组末尾
• 找到就记这个元素，没找到就记-1

接下来重点聊平均时间复杂度：
首先说最坏情况：如果数组是严格递减的（比如5,4,3,2,1），每个元素都要扫到数组最后才能确定没有更大的元素，总操作次数是(n-1)+(n-2)+...+1 = n(n-1)/2，属于O(n²)级别，这是大家都能想到的。

但平均情况就有意思了——假设数组元素是随机分布、互不相等的（这是最符合“平均”的场景），咱们用概率来拆解：
对于任意元素arr[i]，它后面有m = n - i - 1个元素。因为元素随机，每个元素比arr[i]大的概率是1/2（没有任何偏向）。
我们算一下找到第一个更大元素需要的平均比较次数：

• 第1次就找到的概率是1/2，对应1次比较
• 第2次才找到的概率是(1/2)*(1/2)=1/4，对应2次比较
• ...
• 第k次找到的概率是(1/2)^k，对应k次比较
• 如果后面所有m个元素都比它小，概率是(1/2)^m，对应m次比较

把这些情况的期望加起来，最终每个元素的平均比较次数是小于2的（m越大，这个值越接近2，但永远不会超过2）。

这么一来，整个算法的总平均操作次数就是n * 常数，也就是**O(n)**级别。简单说就是，随机情况下，每个元素平均只需要往后看1-2个元素就能找到目标，所以整体平均复杂度是线性的。

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