algorithm - 计算计算复杂度 (Big-O)

Question

Algorithm 1. QUEUESTUFF(n)
Input: Integer n
1) Let Q = an empty Queue
2) For i = 1 to n
3) Q.Enqueue(i)
4) End For
5) For i = 1 to n-1
6) Let X = Q.Dequeue()
7) End For
8) Let X = Q.Dequeue()
Output: The contents of X

What is the computational complexity O(n) for algorithm QUEUESTUFF?

第一个 For 循环只是 n 的，第二个嵌套的循环是 n-1 的。那么这会使O（n）：

O(2n-1) 只需执行 (n + n) - 1

还是通过 (n * n) - 1 执行 O(n^2 - 1)

感谢您的帮助，我只是想澄清一下。我的猜测是，因为我们有一个嵌套的 For 循环，我们必须将 n 乘以 n-1，但是我只是认为我可以通过获得其他人的意见来更好地保证自己。

Answer 1

有两个独立（非嵌套）for循环。 n将项目入队，然后将n项目出队，其复杂度是入队或出队复杂度的 O(n) 倍。如果队列操作复杂度为 O(1)，则过程复杂度为 O(n)，但如果队列操作复杂度为 O(ln n)，则过程复杂度为 O(n ln n)。

Answer 2

感谢 Smoore，得到了答案。由于循环没有嵌套，Big-O 将是 O(2n-1)。