-1 
Algorithm 1. STACKSTUFF(n)
Input: Integer n
1) Let S = an empty Stack
2) Let X = -1
3) For i = 1 to 2n
4) S.Push(i)
5) End For
6) For i = 1 to n
7) Let X = S.Pop()
8) End For
Output: The contents of X

1) What is this algorithm written in pseudo code doing?

据我了解，S.Push(i) 将项目 i 添加到堆栈 S 的顶部。X = S.Pop() 从堆栈 S 的顶部删除项目并将其分配给 X。

2) What is the computational complexity O(n) for algorithm 1, STACKSTUFF?

我相信答案是：O(3n)

第一个循环是 2n，第二个循环是 n，所以 2n+n=3n。

或者......答案是否只是 O(n^2)，因为我们所要做的就是 n*n？

3) If n > 0 then what is returned by the algorithm? What about n < 1

a) 2n
b) -1
c) n-1
d) n+1
e) None of the above

最后一点真的让我很困惑。根据我的理解，如果 n 始终大于 0，则算法将始终返回 n+1，如果 n 始终小于 1，则算法将返回 n-1。然而，这纯粹是猜测工作......

如果我从逻辑上考虑这一点，那么比如说 n 是 3。由于第一个 For 循环是 1 到 2n，那么这意味着我们最终会得到以下堆栈 S={1,2,3,4,5,6}，因为它将每个数字加倍 n 到 S 中。然后第二个 For 循环弹出 3 个数字，因此 X 最终看起来像这样 X={6,5,4}。如果我在那里是正确的...我是否应该假设这只是一个技巧问题而答案是 e，以上都不是？

在继续学习之前，我只是想确保我的理解是正确的。谢谢你的帮助。

4

1 回答 1

1

1) 算法将 1..2n 添加到堆栈中，然后弹出 n 个元素。这意味着 1..n 留在堆栈中，最后一个弹出的元素保留在 X 中。

2）你是对的。该算法具有复杂性：2 + (2n * 1) + (n * 1) = 3n + 2 = O(3n) = O(n)。

3）算法将最后一个弹出的元素存储在X中，然后返回X，最后一个弹出的元素是n+1，所以答案应该是d）n+1。

编辑

解释3：

如果 n > 0：

X := -1
push 2n to the stack
stack = {1, 2, .. n, n + 1, ..., 2n}
pop n elements from the stack and store the popped element in X
first iteration:
   X := stack.pop()
   stack = {1, 2, .. n, n + 1, ..., 2n - 1}
   X = 2n
... until we have popen n numbers. 
stack = {1, 2, .. n}
X = n + 1

如果 n < 1

X := -1
because n < 1 we won't do any iterations in the loops
so X will not change and still be -1
于 2013-05-05T21:28:27.070 回答