如何计算空间复杂度？

跟着做题的时候发现要计算复杂度==
发现自己完全就不会计算空间复杂度，看大家计算的，同一个算法，有的人写O(1)，有的人写O(n)，网上翻了一些关于space complexity的博客，还是云里雾里的……
有人可以稍微解释下吗？

就比如下面代码，空间复杂度是多少呢？

1. private static boolean PermutationString2(String str1, String str2) {
   
2.         if (str1 == null || str2 == null) {
   
3.             return false;
   
4.         } else if (str1.length() != str2.length()) {
   
5.             return false;
   
6.         }
   
7. 
   
8.         int[] checkPermutation = new int[256];
   
9.         int stringLength = str1.length();
   
10. 
    
11.         for (int i = 0; i < stringLength; i++) {
    
12.             char c = str1.charAt(i);
    
13.             checkPermutation[c]++;
    
14.         }
    
15. 
    
16.         for (int i = 0; i < stringLength; i++) {
    
17.             int c = str2.charAt(i);
    
18.             if (checkPermutation[c] == 0) {
    
19.                 return false;
    
20.             }
    
21.             checkPermutation[c]--;
    
22.         }
    
23.         return true;
    
24.     }

复制代码

个人的理解是额外的内存空间只是一个Int类型，而int类型只是256个，并不是随着输入而改变，所以是O(1)
但是下面这个呢？

1. private static boolean PermutationString3(String str1, String str2) {
   
2.         if (str1 == null || str2 == null) {
   
3.             return false;
   
4.         } else if (str1.length() != str2.length()) {
   
5.             return false;
   
6.         }
   
7. 
   
8.         char[] strArray1 = str1.toCharArray();
   
9.         char[] strArray2 = str2.toCharArray();
   
10.         Arrays.sort(strArray1);
    
11.         Arrays.sort(strArray2);
    
12.         for (int i = 0; i < str1.length(); i++) {
    
13.             if (strArray1[i] != strArray2[i]) {
    
14.                 return false;
    
15.             }
    
16.         }
    
17.         return true;
    
18.     }

复制代码

因为输入的String类型不知道是多少个，默认是不是就是n了？然后因为新建了两个字符串数组，而数组的长度是根据input String来决定的，所以空间复杂度应该是O(2n)？

那HashMap这一类的呢？又该如何计算？

readman 发表于 2014-6-25 00:46
第一个理论上是n, 我这里的256是个假设string是ascii, 当然如果是最差情况, string可能是一个长度为n, 并且 ...

n个字符都不相同也是O(1)吧，毕竟数组就是256这么大，查了查资料，其实跟多大没有关系，即便是O(10000000)依然是O(1),只要你开辟的是固定的数组大小

如果你开辟的是一个随着input而改变的空间，例如input int: n, 然后开辟了int[n]，这样即使n=10, 也应该是O(n)，不知道我这样说的对不对

那我用HashMap实现这个题的话，Space complexity应该也是O(n)吧？
毕竟新建一个HashMap，put值的话是根据input String中不同字符的个数来定的？

第一个理论上是n, 我这里的256是个假设string是ascii, 当然如果是最差情况, string可能是一个长度为n, 并且n个字符都不相同的(我实在不知道这种情况什么时候发生).

第二个肯定是n, 假设string为n长度, char [] 就是一个n个char的array

我认为你的理解是对的，根据输入变量相应改变的才是空间复杂度。
你的例子里，第一个O（1），第二个是O（n）或者说O（n+m），O（2n）等同于O（n）。

用hashmap的话，我的理解还是常量，本质上和第一种解法是一致的，只是可能的数据量是一个比较大的数（http://www.ruanyifeng.com/blog/2 ... code_and_utf-8.html），理论上如果这个字符串每个字符不一致那么就是O(n)，但是我们讨论复杂度的时候都是基于n趋向于无穷大，所以只要是一个可以预测的固定大小，那么应该作为O(1)。
新建一个HashMap不需要给定N空间，是根据新的Key来分配空间，Key的数量是可预测的。（C需要给定Map的长度？）