此字符串处理代码的空间复杂度是多少？ [英] What is the space complexity of this string manipulation code?

问题描述

这段代码来自《破解编码》采访书。

This piece of code is from Cracking the Coding interview book.

public static boolean isUniqueChars2(String str) {
    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val]) return false;
        char_set[val] = true;
    }
    return true;
}

作者提到，

时间复杂度为O（n），其中n是字符串的长度，
空间复杂度为O（n）。

Time complexity is O(n), where n is the length of the string, and space complexity is O(n).

我了解时间复杂度为O（n），但我不了解空间复杂度如何为O（n）

I understand time complexity being O(n) but I don't understand how could space complexity be O(n)

我的想法：
char_set将保持大小为256的数组，无论输入（str）大小如何。
即使 str的长度为100,000，char_set仍然是256个元素的数组。
因此，我认为，由于此函数的内存要求不会随输入大小而变化，并且保持为256不变，因此空间复杂度是恒定的，即O（1）。

My thinking: char_set will remain an array of size 256 no matter what the input (str) size is. Even if the length of "str" is 100,000, char_set is still a 256 element array. So I thought, since memory requirements for this function does not change with the size of the input and remain a constant 256, the space complexity is constant, i.e., O(1).

有人可以解释一下，如果我错了（为什么？）

Can someone explain, if I am wrong (and, why?)

非常感谢。

推荐答案

该示例中的空间复杂度为O（N），因为该字符串是作为参数接收的。我们不完全知道它的大小，并且考虑到空间复杂度有关算法时间的内存消耗的建议，它会根据 str的大小而有所不同。因此，应该使用N。

The space complexity in that example is O(N) because the string is received as parameter; we don't know exactly it's size, and taking into account that the space complexity advices about the memory consumption in time of the algorithm, it will vary depending on the size of "str". Because of that N should be used.

例如，完全相同的情况发生：

Exactly the same happens if I have for example:

public void someMethod(int a[], char s, int w){...}

由于 a []（我们不知道它的大小），它将是O（N）。

It will be O(N) because of "a[]" (we don't know it's size).

另一方面：

public void someMethod(char s, int a, int x){...}

它将是O（1）（常数）。由于我们已经知道分配给必要属性的内存。

It will be O(1) (constant). Due we already know the memory allocated for the necessary attributes.

希望它会有所帮助。

这篇关于此字符串处理代码的空间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！