我需要使用求和/西格玛表示法预测算法相对于其输入大小的平均案例效率，以得出最终答案。许多资源使用求和来预测最坏情况，我找不到人解释如何预测平均情况，因此赞赏分步答案。
该算法包含一个嵌套的 for 循环，基本操作位于最里面的循环中：
[代码已编辑]
编辑：基本操作的执行，如果已输入第二个 for 循环，并且没有中断或返回语句，它将始终在第二个 for 循环内执行。但是：第一个 for 循环的末尾具有 return 语句，该语句取决于基本操作中生成的值，因此数组的内容确实会影响每次运行算法执行基本操作的总次数。
传递给算法的数组具有随机生成的内容
我认为预测的平均案例效率是 (n^2)/2，使其成为 n^2 的增长阶/n^2 的大 Theta，但我不知道如何使用求和从理论上证明这一点。 非常感谢回答！
TL;DR：如果"基本操作"复杂度Θ(1)并且没有return、break或goto运算符，那么您在平均情况下的代码复杂性是Θ(n²)的。
说明：平均大小写复杂度只是给定输入大小的代码中操作数的预期。
假设您的代码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.因此，给定数组大小的预期运算数(它只是给定n的所有可能A的T(A, n)的算术平均值)正好等于它们中的每一个：
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)