一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1835|回复: 3
收起左侧

[算法题] 如何计算空间复杂度?

[复制链接] |试试Instant~ |关注本帖
sanguine 发表于 2014-6-24 22:19:29 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
跟着做题的时候发现要计算复杂度==
发现自己完全就不会计算空间复杂度,看大家计算的,同一个算法,有的人写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.         int[] checkPermutation = new int[256];
  8.         int stringLength = str1.length();

  9.         for (int i = 0; i < stringLength; i++) {
  10.             char c = str1.charAt(i);
  11.             checkPermutation[c]++;
  12.         }

  13.         for (int i = 0; i < stringLength; i++) {
  14.             int c = str2.charAt(i);
  15.             if (checkPermutation[c] == 0) {
  16.                 return false;
  17.             }
  18.             checkPermutation[c]--;
  19.         }
  20.         return true;
  21.     }
复制代码
个人的理解是额外的内存空间只是一个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.         char[] strArray1 = str1.toCharArray();
  8.         char[] strArray2 = str2.toCharArray();
  9.         Arrays.sort(strArray1);
  10.         Arrays.sort(strArray2);
  11.         for (int i = 0; i < str1.length(); i++) {
  12.             if (strArray1[i] != strArray2[i]) {
  13.                 return false;
  14.             }
  15.         }
  16.         return true;
  17.     }
复制代码
因为输入的String类型不知道是多少个,默认是不是就是n了?然后因为新建了两个字符串数组,而数组的长度是根据input String来决定的,所以空间复杂度应该是O(2n)?

那HashMap这一类的呢?又该如何计算?
 楼主| sanguine 发表于 2014-6-25 08:59:39 | 显示全部楼层
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中不同字符的个数来定的?
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2014-6-25 00:46:25 | 显示全部楼层
第一个理论上是n, 我这里的256是个假设string是ascii, 当然如果是最差情况, string可能是一个长度为n, 并且n个字符都不相同的(我实在不知道这种情况什么时候发生).

第二个肯定是n, 假设string为n长度, char [] 就是一个n个char的array
回复 支持 反对

使用道具 举报

t__c___ 发表于 2014-7-1 03:43:47 | 显示全部楼层
我认为你的理解是对的,根据输入变量相应改变的才是空间复杂度。
你的例子里,第一个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的长度?)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 20:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表