登录
  • #刷题

如何计算空间复杂度?

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

发现自己完全就不会计算空间复杂度,看大家计算的,同一个算法,有的人写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]
3条回复
热度排序

发表回复