6

这段代码来自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)。

我理解时间复杂度是 O(n) 但我不明白空间复杂度怎么可能是 O(n)

我的想法：无论输入（str）大小是多少，char_set 都将保持一个大小为 256 的数组。即使“str”的长度是 100,000，char_set 仍然是一个 256 元素的数组。所以我想，由于这个函数的内存需求不会随着输入的大小而改变并且保持一个常数256，所以空间复杂度是常数，即O(1)。

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

太感谢了。

4

2 回答 2

1

该示例中的空间复杂度为 O(N)，因为字符串是作为参数接收的；我们并不确切地知道它的大小，并且考虑到空间复杂度对算法时间内存消耗的影响，它会根据“str”的大小而有所不同。因为应该使用N。

例如，如果我有完全相同的情况：

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

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

另一方面：

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

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

希望能帮助到你。

于 2018-04-08T23:11:53.107 回答
0

这有点复杂，我认为：

在遇到某个字符两次之前的最大迭代次数是构建字符串的字母表的大小。

如果这个大小是有限的，则时间复杂度为 O(1)，如果不是，则布尔数组的大小不能是有限的，因此，空间复杂度将为 O(n)。

于 2013-03-13T22:00:11.003 回答