计算堆栈搜索的空间复杂性 [英] Calculating Space Complexity of Stack Search

问题描述

在堆栈和搜索功能的情况下，我明白时间复杂度是 O（n）因为它取决于堆栈中元素的数量。在这种情况下，空间复杂度是多少？由于没有变量，或者根据元素的数量而使搜索消耗额外的内存，因此它将成为 O（1） O （n）？

Ex功能：

  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; 
} 
  

有人可以逐步细分如何计算这个空间复杂性

解决方案

对于 Stack.search 。

然而，简单看一下OpenJDK源代码，显示它是以 Vector.lastIndexOf（） ，而是只有几个帮助变量的线性扫描。所以是的，O（1）空间在实践中。

having a bit of issues understanding space complexity for a method.

In the case of a stack and a search function, I understand that time complexity is O(n) since it depends on the amount of elements in the stack. What would the space complexity be in this case? Would it be O(1) since there are no variables or does the search consume extra memory based off the amount of elements and cause it to be O(n)?

Ex Function:

return stack.search(item) != -1

Edit:

Here is the built in function in question:

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;
}

Can someone provide a step by step breakdown of how to calculate space complexity for this?

解决方案

Neither time nor space complexity appears to be documented in the Javadoc for Stack.search.

However, a brief look at the OpenJDK source code shows that it's implemented in terms of Vector.lastIndexOf(), which in turn is a linear scan with just a couple of helper variables. So yes, O(1) space in practice.

这篇关于计算堆栈搜索的空间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！