toCharArray() 在 Big O 中是否消耗 space

Question

在计算算法的 space 复杂度时，我们被告知找出额外 space 的最简单方法是创建数据结构，如 Set、Map、Stack 等。

以下面的代码为例，尊重字符串(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 < last){
        char temp = strArray[first];
        strArray[first++] = strArray[last];
        strArray[last--] = temp;
    }


    return String.valueOf(strArray);
}

将 str 转换为字符数组是否消耗 space

Answer 1

根据 String's javadoc，toCharArray 创建 "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"。因此，调用 toCharArray 的复杂度为 O(n) space。

toCharArray() 在 Big O 中是否消耗 space

Does toCharArray() consumes space in Big O

java

arrays

string

big-o

space-complexity