toCharArray()在大O表示法中消耗空间吗?

huangapple go评论79阅读模式
英文:

Does toCharArray() consumes space in Big O

问题

在计算算法的空间复杂度时,我们被告知查找额外空间的最简单方法是创建像Set、Map、Stack等数据结构。

以反转字符串为例的以下代码(在Java中):

private String reverse(String string){

    if (string == null || string.length() == 0) return string;

    char[] strArray = string.toCharArray(); // 这会消耗空间吗?

    int first = 0, last = strArray.length - 1;

    while (first < last){
        char temp = strArray[first];
        strArray[first++] = strArray[last];
        strArray[last--] = temp;
    }

    return String.valueOf(strArray);
}

将字符串转换为字符数组会消耗空间吗?

英文:

In calculating the space complexity of algorithms, we're told the easiest way to find out about additional space is the creation of a data structure like Set, Map, Stack etc.

Take the below code as example that reveres a string (In Java)

private String reverse(String string){

    if (string == null || string.length() == 0) return string;

    char[] strArray = string.toCharArray(); // Does this consume space?

    int first = 0, last = strArray.length - 1;

    while (first &lt; last){
        char temp = strArray[first];
        strArray[first++] = strArray[last];
        strArray[last--] = temp;
    }


    return String.valueOf(strArray);
}

Does converting the str to a character array consume space

答案1

得分: 5

根据 String 的 Java 文档toCharArray 方法会创建一个“新分配的字符数组,其长度为此字符串的长度,并且其内容被初始化为包含此字符串所表示的字符序列”。因此,调用 toCharArray 方法的空间复杂度为 O(n)。

英文:

According to String's javadoc, toCharArray creates "a newly allocated character array whose length is the length of this string and whose contents are initialized to contain the character sequence represented by this string". Therefore, calling toCharArray has an O(n) space complexity.

huangapple
  • 本文由 发表于 2020年4月10日 01:27:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/61126805.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定