我有算法: 输入:X，一个大小为 n 的一维数值数组
Let A = an empty 1-D numerical array of size n
For i = 0 to n-1
Let s = X[0]
For j = 1 to i
Let s = s + X[j]
End For
Let A[i] = s /(i+1)
End For
输出:一个 n 元素数组 A 的数字使得 A[i] 是元素 X[0],X[1], … ,X[i]
的平均值我正在尝试编写 T(n) 公式并计算它，如何在 for 循环 i = 0 到 n-1 中编写 for 循环 J = 1 到 i。
什么是 T(n) 公式？
T(n) 是算法执行所需的时间。 t(n) 将用于计算大 O ( O(n) )。所以现在我有 T(n) = 2n+2(n-1)+5i(n-1)+6(n-1)+1。因为我计算了算法中的写入、读取和操作。不知道公式写好了没有。
最佳答案
我不是很清楚你的问题，但是还是
如何在for循环i = 0 to n-1中写for循环J = 1 to i？
你写循环的方式没问题，它会做你想做的..
什么是 T(n) 公式？
您可以注意到该算法将使第二个循环运行
0 次 i=0,
1 当i=1时，
2 当i=2时，
.
.
.
等等..
这将一直持续到 n-1，因此复杂度达到 0 + 1 + 2 + .... + n-1 的总和，即n*(n-1)/2。这是渐近 O(n^2)
关于algorithm - 计算/计算for循环内for循环的原始操作，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26532371/