计算给定程序的基本操作

Question

应该显示以下伪代码的操作计数：

Algorithm prefixAverages(A)
 Input array A of n numbers
 Output array B of n numbers such that B[i] is the average
 of elements A[0], A[1], … , A[i]

for i = 0 to n - 1 do
   b = 0
   for j = 0 to i do
       b = b + A[j]
       j++;
   B[i] = b / (i + 1)
return B

但我看不到内部 for 循环的计数是如何达到的。它说对于 case i=0; j=0; 内部 for 循环运行s 两次？但令我印象深刻的是，它应该只运行一次才能看到 0 < 0。任何人都可以深入了解给定操作计数的来源或提供他们自己的操作计数吗？

这是假设原始操作是：

作业
数组访问
数学运算符（+、-、/、*）
比较
Increment/Decrement（伪装的数学）
Return 语句

如果有任何不清楚的地方或您需要更多信息，请告诉我

Answer 1

当您关注的文章说 "for var <- 0 to var2" 时，它就像 "for (var = 0; var <= var2; var++), so yes, when i = 0, it enters the "for" 两次（一次是在 i = 0 时，一次是在 i = 1 时，然后熄灭）。（如果英语不好请见谅）

编辑改进：当我计算一个程序的复杂度时，我唯一感兴趣的是大O复杂度；在这种情况下，'i' 循环运行 'n' 次，'j' 循环运行 'i' 次，所以 'i'循环运行s(1+2+3+...+n)次，也就是n(n+1)/2次，也就是O(n**2)的复杂度。

在第一行，你有一个赋值（i = something）和一个比较（i <= n-1）（“2 次操作”）每个 i 值，最后一个值是 i= n，它从 i=0 开始执行这 2 个操作，直到 i=n，并且因为它们是 n+1 个值（从 0 到 n），所以这一行执行 2(n+1) 个操作。

第二行有点明显，进入循环n次（从i=0开始，直到i=n-1）

第二次循环，做了2件事，赋值，比较（和第一次循环一样），做了i+2次（比如i=0时，进入循环1 次，但它必须做 i=1 赋值，并且 1<=0 比较，所以它总共 2 次），所以它做这个微积分 2(i+2) 次，但它这样做是因为 i= 0，直到 i=n-1，所以要计算所有这些，我们必须求和（从 i=0 到 i=n-1 的总和：2(i+2)) = 2((sum of i from 0 到 n-1) + (从 i=0 到 i=n-1 的 2 之和)) = 2((n(n-1)/2) + 2n) = n(n-1) + 4n = n "2 - n + 4n = n"2 + 3n.

稍后我会继续，希望我到目前为止的回答对您有所帮助。（再次抱歉，如果英语不好）

计算给定程序的基本操作

Counting the basic operations of a given program

c++

performance

runtime

big-o