分析 Big Oh 表示法伪代码
我无法理解算法分析。我似乎可以识别线性或平方算法，但完全迷失了 nlogn 或 logn 算法，这些似乎主要源于 while 循环？这是我正在看的一个例子：
Algorithm Calculate(A,n)
Input: Array A of size n
t←0
for i←0 to n-1 do
if A[i] is an odd number then
Q.enqueue(A[i])
else
while Q is not empty do
t←t+Q.dequeue()
while Q is not empty do
t←t+Q.dequeue()
return t
我最好的猜测是 for 循环执行了 n 次，它的嵌套 while 循环 q 次使得 NQ 和最后的 while 循环也 Q 次导致 O(NQ +Q) 这是线性的？
I'm having trouble getting my head around algorithm analysis. I seem to be okay identifying linear or squared algorithms but am totally lost with nlogn or logn algorithms, these seem to stem mainly from while loops? Here's an example I was looking at:
Algorithm Calculate(A,n)
Input: Array A of size n
t←0
for i←0 to n-1 do
if A[i] is an odd number then
Q.enqueue(A[i])
else
while Q is not empty do
t←t+Q.dequeue()
while Q is not empty do
t←t+Q.dequeue()
return t
My best guess is the for loop is executed n times, its nested while loop q times making NQ and the final while loop also Q times resulting in O(NQ +Q) which is linear?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先，我们假设 Q 最初是空的。
Q 最多只会以与主循环执行相同的速率增长。例如，如果到目前为止我们已经迭代了 3 次以上，那么 Q 最多是 3 个元素大。所以当内部while循环执行时，它最多只能执行到'i'的当前值。这意味着内部循环不是 n^2 上的真实情况（无论如何，这不是您声称的）。然而，由于 Q 最多只能是“i”个元素大，因此我们知道 O(calculate) <= O(2N)。由于在 O 表示法中我们实际上并不关心标量，因此它是 O(N)。
除非我错了:)
First, lets assume that Q is initially empty.
Q will only grow at most at the same rate of the execution of the main loop. For example, if we have iterated over 3 times so far, then Q is at most 3 elements large. So when the inner while loop executes, it can at most only execute up to the current value of 'i'. This means that the inner loop isn't a true case on n^2 (which isn't something you claimed anyway). However, since Q can at most only be 'i' elements large, thus we know that O(calculate) <= O(2N). And since in O notation we really don't care about scalars, then it is O(N).
Unless I'm wrong :)