正在计算堆栈搜索的 Space 复杂度

Question

在理解 space 方法的复杂性时遇到一些问题。

在堆栈和搜索函数的情况下，我知道时间复杂度是 O(n)，因为它取决于堆栈中元素的数量。在这种情况下，space 的复杂度是多少？是 O(1) 因为没有变量还是搜索会根据元素的数量消耗额外的内存并导致它是 O(n)？

前函数：

return stack.search(item) != -1

编辑：

这是有问题的内置函数：

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}
public synchronized int lastIndexOf(Object o, int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

    if (o == null) {
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

有人可以详细说明如何为此计算 space 复杂度吗？

Answer 1

我没明白你说的O(n)的意思。 Stack 是 O(1) 的存储（push）时间和 O(1) 的检索（pop）时间。

没有定义为搜索正确堆栈数据结构的操作。 Stack 只是以后进先出的方式工作。当你添加一个新项目时，你将它添加到顶部，当你检索一个项目时，你只有一个选项，顶部。因此，push 和 pop 操作的时间复杂度都是 O(1)。

要谈space复杂性，我们需要知道问题是什么。如果您需要同时在堆栈中存储 n 个项目，那么 space 复杂度为 O(n)。但是您也可以在 O(1) space 中存储 n 项。您可以推送和弹出每个项目，因此您只使用 1 space.

那么这个 Java 实施中发生了什么？

他们似乎只是简单地实现了搜索方法，以防万一，也许有人会需要，我不知道。但它只是违反了堆栈合同。

如果使用栈上查找，那么时间复杂度是O(n)，实际上已经不是栈了。 Space 复杂度是 O(1)，你猜对了。它只会使用 1 个额外的变量，不会随着堆栈大小的增加而增加。

编辑：抱歉，我没有意识到这是 Java 的堆栈实现特定问题。我正在编辑我的答案以涵盖 Java 实施。

Answer 2

时间和 space 复杂性似乎都没有记录在 Stack.search 的 Javadoc 中。

但是，简单看一下 OpenJDK 源代码就会发现 it's implemented in terms of Vector.lastIndexOf(), which in turn is a linear scan with just a couple of helper variables。所以是的，O(1) space 在实践中。

正在计算堆栈搜索的 Space 复杂度

Calculating Space Complexity of Stack Search

java

algorithm

big-o

stack

data-structures