如何计算空间复杂度？

跟着做题的时候发现要计算复杂度==

发现自己完全就不会计算空间复杂度，看大家计算的，同一个算法，有的人写O(1)，有的人写O(n)，网上翻了一些关于space complexity的博客，还是云里雾里的……

有人可以稍微解释下吗？

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

 private static boolean PermutationString2(String str1, String str2) {[br][/br][br][/br]        if (str1 == null || str2 == null) {[br][/br][br][/br]            return false;[br][/br][br][/br]        } else if (str1.length() != str2.length()) {[br][/br][br][/br]            return false;[br][/br][br][/br]        }[br][/br][br][/br]        int[] checkPermutation = new int[256];[br][/br][br][/br]        int stringLength = str1.length();[br][/br][br][/br]        for (int i = 0; i < stringLength; i++) {[br][/br][br][/br]            char c = str1.charAt(i);[br][/br][br][/br]            checkPermutation[c]++;[br][/br][br][/br]        }[br][/br][br][/br]        for (int i = 0; i < stringLength; i++) {[br][/br][br][/br]            int c = str2.charAt(i);[br][/br][br][/br]            if (checkPermutation[c] == 0) {[br][/br][br][/br]                return false;[br][/br][br][/br]            }[br][/br][br][/br]            checkPermutation[c]--;[br][/br][br][/br]        }[br][/br][br][/br]        return true;[br][/br][br][/br]    }

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

但是下面这个呢？

private static boolean PermutationString3(String str1, String str2) {[br][/br][br][/br]        if (str1 == null || str2 == null) {[br][/br][br][/br]            return false;[br][/br][br][/br]        } else if (str1.length() != str2.length()) {[br][/br][br][/br]            return false;[br][/br][br][/br]        }[br][/br][br][/br]        char[] strArray1 = str1.toCharArray();[br][br][/br]        char[] strArray2 = str2.toCharArray();[br][br][/br]        Arrays.sort(strArray1);[br][/br][br][/br]        Arrays.sort(strArray2);[br][/br][br][/br]        for (int i = 0; i < str1.length(); i++) {[br][/br][br][/br]            if (strArray1[i] != strArray2[i]) {[br][/br][br][/br]                return false;[br][/br][br][/br]            }[br][/br][br][/br]        }[br][/br][br][/br]        return true;[br][/br][br][/br]    }因为输入的String类型不知道是多少个，默认是不是就是n了？然后因为新建了两个字符串数组，而数组的长度是根据input String来决定的，所以空间复杂度应该是O(2n)？[br][/br][br][/br]那HashMap这一类的呢？又该如何计算？[/i][/i]