计算算法的 T(n) 时间复杂度
我正在寻找一些关于计算算法时间效率的澄清，特别是 T(n)。尽管我相信下面的算法是一个值得学习的很好的例子，但它的效率并不高。我希望对代码中的操作总和进行逐行确认：
伪代码
1. Input: array X of size n
2. Let A = an empty array of size n
3. For i = 0 to n-1
4. Let s = x[0]
5. For j = 0 to i
6. Let sum = sum + x[j]
7. End For
8. Let A[i] = sum / (i+1)
9. End For
10. Output: Array A
我计算 T(n)
1. 1
2. n
3. n
4. n(2)
5. n(n-1)
6. n(5n)
7. -
8. n(6)
9. -
10. 1
T(n) = 1 + n + n + 2n + n^2 - n + 5n^2 + 6n + 1
= 6n^2 + 9n + 2
所以，T (n) = 6n^2 + 9n + 2 是我得出的结果，由此我推导出 O(n^2) 的 Big-O。 我在计算中犯了什么错误（如果有的话）...
编辑：...计算导出 T(n) 的原始操作？
I am looking for some clarification in working out the time efficiency of an Algorithm, specifically T(n). The algorithm below is not as efficient as it could be, though it's a good example to learn from I believe. I would appreciate a line-by-line confirmation of the sum of operations in the code:
Pseudo-code
1. Input: array X of size n
2. Let A = an empty array of size n
3. For i = 0 to n-1
4. Let s = x[0]
5. For j = 0 to i
6. Let sum = sum + x[j]
7. End For
8. Let A[i] = sum / (i+1)
9. End For
10. Output: Array A
My attempt at calculating T(n)
1. 1
2. n
3. n
4. n(2)
5. n(n-1)
6. n(5n)
7. -
8. n(6)
9. -
10. 1
T(n) = 1 + n + n + 2n + n^2 - n + 5n^2 + 6n + 1
= 6n^2 + 9n + 2
So, T(n) = 6n^2 + 9n + 2 is what I arrive at, from this I derive Big-O of O(n^2).
What errors, if any have I made in my calculation...
Edit: ...in counting the primitive operations to derive T(n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您的结果 O(n^2) 是正确的，并且由两个嵌套循环给出。 推导。
我更喜欢通过观察嵌套循环得出这样的
Your result O(n^2) is correct and is given by the two nested loops. I would prefer the derivation like
that follows from observing the nested loops.
我不太确定你的方法，但 O(n^2) 似乎是正确的。在第一个循环的每次迭代中，您都会对先前的元素执行一个子循环。因此，您第一次查看 1，第二次查看 2，然后查看 3，然后...然后最后一次查看 n。这相当于 1 到 n 的总和，复杂度为 n^2。
I'm not really sure on your methodology but O(n^2) does seem to be correct. At each iteration through the first loop you do a sub loop of the previous elements. Therefore you're looking at 1 the first time 2 the second then 3 then... then n the final time. This is equivalent to the sum from 1 to n which gives you complexity of n^2.