代码片段平均情况下的Θ表达式解析及内层循环期望次数求解

先明确代码逻辑：外层循环遍历i = 0到n-1，内层循环从j=0开始，每执行一次sum++，直到找到A[j] = i才停止。注意内层循环的执行次数等于i在数组A中的索引值——比如i在A的第k个位置（索引k），那么j会从0走到k-1，一共执行k次循环（j=k时触发终止条件，不进入循环）。

因为A是0到n-1的随机排列，每个元素出现在任意索引位置的概率均等：

• 对于任意i，它出现在索引k（k从0到n-1）的概率都是1/n。

接下来计算单个i对应的内层循环执行次数的期望：
单个i的期望执行次数E(k_i)等于所有可能的索引k乘以对应概率的总和，即：

E(k_i) = (0*(1/n)) + (1*(1/n)) + (2*(1/n)) + ... + ((n-1)*(1/n))

这是一个等差数列求和，化简后：

E(k_i) = (1/n) * [n(n-1)/2] = (n-1)/2

外层循环共执行n次，所以总的内层循环期望执行次数是：

总期望 = n * E(k_i) = n*(n-1)/2 = (n² - n)/2

这个结果的主导项是n²/2，因此平均情况下的Θ表达式为Θ(n²)。

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