c++ - 使用求和预测算法的理论平均情况效率和增长顺序

Question

我需要使用求和/西格玛表示法预测算法相对于其输入大小的平均案例效率，以得出最终答案。许多资源使用求和来预测最坏情况，但我找不到有人解释如何预测平均情况，因此不胜感激分步回答。

该算法包含一个嵌套的 for 循环，最内层循环中的基本操作:

[代码编辑]

编辑: 如果进入第二个 for 循环并且没有 break 或 return 语句，则基本操作的执行将始终在第二个 for 循环内执行。但是:第一个 for 循环的末尾有 return 语句，它取决于基本操作中产生的值，因此数组的内容确实会影响算法每次运行时基本操作将执行的总次数。

传递给算法的数组具有随机生成的内容

我认为预测的平均案例效率是 (n^2)/2，使其增长 n^2 阶/n^2 的大 Theta，但我不知道如何使用求和从理论上证明这一点。非常感谢您的回答!

Answer 1

TL;DR:如果“基本操作”复杂度为 Θ(1)，则平均情况下您的代码复杂度为 Θ(n²)并且它没有 return、break 或 goto 运算符。

说明:平均情况下的复杂度只是在给定输入大小的情况下对代码中操作数的预期。

假设 T(A, n) 是您的代码执行给定大小为 n 的数组 A 的操作数。很容易看出这一点

T(A, n) = 1  +                // int k = ceil(size/2.0);
    n * 2 + 1 +               // for (int i = 0; i < size; i++){
    n * (n * 2 + 1) +         // for(int j = 0; j < size; j++){
    n * n * X +               // //Basic operation 
    1                         // return (some int);

其中 X 是您的“基本操作”中的操作数。如我们所见，T(A, n) 不依赖于数组 A 的实际内容。因此，给定数组大小的预期操作数(这只是 T(A, n) 对于给定 n 的所有可能 A 的算术平均值) 完全等于它们中的每一个:

T(n) = T(A, n) = 3 + n * 2 + n * n * (2 + X)

如果我们假设 X = Θ(1)，则此表达式为 Θ(n²)。

即使没有这个假设，我们也可以进行估算:如果 X = Θ(f(n))，那么您的代码复杂度为 T(n) = Θ(f(n) n²)。例如，如果 X 是 Θ(log n)，则 T(n) = Θ(n² log n)