使用堆栈的大 O 是 O(1) 吗？

Question

我正在尝试解决一些算法问题。我有这个：

编写一个 reverseWords() 方法，将一条消息作为字符数组并反转单词的顺序。

例如：

char[] message = { 'c', 'a', 'k', 'e', ' ',
            'p', 'o', 'u', 'n', 'd', ' ',
            's', 't', 'e', 'a', 'l' };

结果我们应该得到：

steal pound cake

建议的实施方式是：

public static void reverseWords(char[] message) {

    // first we reverse all the characters in the entire message array
    // this gives us the right word order
    // but with each word backward
    reverseCharacters(message, 0, message.length - 1);

    // now we'll make the words forward again
    // by reversing each word's characters

    // we hold the index of the *start* of the current word
    // as we look for the *end* of the current word
    int currentWordStartIndex = 0;
    for (int i = 0; i <= message.length; i++) {

        // found the end of the current word!
        if (i == message.length || message[i] == ' ') {

            // if we haven't exhausted the array, our
            // next word's start is one character ahead
            reverseCharacters(message, currentWordStartIndex, i - 1);
            currentWordStartIndex = i + 1;
        }
    }
}

private static void reverseCharacters(char[] message, int leftIndex, int rightIndex) {

    // walk towards the middle, from both sides
    while (leftIndex < rightIndex) {

        // swap the left char and right char
        char temp = message[leftIndex];
        message[leftIndex] = message[rightIndex];
        message[rightIndex] = temp;
        leftIndex++;
        rightIndex--;
    }
}

如您所见，它遍历数组两次，N + N，所以它是 O(n)

但我认为使用堆栈会是更好的方法，如下所示：

public static void reverseWords(char[] message) {
        Stack<String> stack = new Stack<>();
        String word = "";

        int i = 0;
        while (i < message.length) {
            if (message[i] != ' ') {
                word = word + message[i];
            }
            else {
                stack.push(word);
                word = "";
            }
            i++;
        }

        stack.push(word);

        int j = 0;
        while (!stack.isEmpty()) {
            String wordStack = "";
            wordStack = stack.pop();
            for (i = 0; i < wordStack.length(); i++) {
                message[j] = wordStack.charAt(i);
                j++;
            }
            if (stack.size() > 0) {
                message[j] = ' ';
                j++;
            }
        }

在这种情况下，它只遍历数组并从堆栈中插入和删除项目，它应该是 O(1)。我的意思是它也是 O(n)，但不同之处在于你只遍历数组一次。

你怎么看？我说的对不对？

谢谢

Answer 1

第一个解决方案应该更快，但它们都在 O(n) 中。

Answer 2

您无法在 O(1) 中解决此任务。

为了反转消息（字符数组）中的单词，您显然需要至少遍历整个数组一次，并且可能不止一次，正如我们在各种解决方案中看到的那样。

但是你绝对不能在不真正阅读完整数组到最后的情况下反转所有单词。读取数组到最后是一个 O(n) 操作，根据定义，n 是数组的长度。

当运行时间（或所需的步骤数）恒定或至少不依赖于输入的长度时，操作为 O(1)。就输入的长度而言，读取其整个输入的方法不能为 O(1)。

请注意，“关于...”部分非常重要 - n 在 O(n) 中的含义很重要。

例如，在散列table（或HashMap，在Java术语中）中搜索元素通常被认为是一个O(1)操作，因为它不依赖于地图中已有的元素数量。然而，它在很大程度上取决于要搜索的元素的长度 - 它需要计算该元素的哈希值，这需要遍历元素的整个长度，因此这显然是一个 O(n) 操作到输入的长度。然而，由于元素本身的长度与整个 hashmap 的潜在大小相比通常可以忽略不计，因此这个 O(n) 是无关紧要的。而且由于在哈希映射中搜索确实与映射的大小无关，所以整个事情被认为是 O(1)。

另请注意，O(1) 并不意味着该算法对于每个给定输入都会很快。它只意味着运行时间是恒定的，而不是它很低。通常 O(1) 算法具有高固定成本和高常数因子，这对于大输入是可接受的table，但对于小输入，具有低固定开销的 O(n) 算法可能更快。

以散列映射为例，如果映射中有 5 个元素，并且您想检查映射是否包含给定值，那么 much 更快遍历所有 5 个元素，而不是使用通用算法 - 计算搜索元素的哈希值并使用它来预测它应该存储在地图中的位置。地图中有 10 个或 50 个元素也是如此，但有 500 万个，情况就不同了，有 50 亿个，那就是 much不同的故事。

使用堆栈的大 O 是 O(1) 吗？

Big O using a stack is it O(1)?

java

big-o