英文:
Big O Notation for space complexity of converting a string to char array
问题
根据给定的字符串String str = "absdf"；长度为N，如果我们使用以下方法将相同的字符串转换为字符数组 -
char[] arr = str.toCharArray();
这会被视为额外空间复杂度为O(N)还是O(1)？
英文:
Given a string String str= "absdf"; of N length and if we convert the same string to char Array using -
char [] arr=str.toCharArray();.
Is it consider to be an extra space of O(N) or it will be O(1)?
答案1
得分: 2
这是 O(N)，如 @andy 所建议的，String.toCharArray() 的实现大致如下：
public char[] toCharArray() {
char result[] = new char[value.length];
// 复制内容
return result;
}
英文:
It is O(N) as suggested by @andy, the implementation of String.toCharArray() is something like:
public char[] toCharArray() {
char result[] = new char[value.length];
// copy the contents
return result;
}
答案2
得分: 1
Time Complexity将会是O(N)。类似于创建一个新的长度与字符串相等的数组，并将字符串复制到字符数组中。创建数组需要O(N)的时间，复制需要O(N)的时间。因此，总的最坏情况复杂度将会是O(N)。
英文:
Time Complexity will be O(N). Similar to creating a new Array equal to the length of the String and copying the String to the Character Array. Creating an array takes O(N) time and copying takes O(N). So total worst case complexity will be O(N).
答案3
得分: 1
它的时间复杂度是O(N)
public char[] toCharArray() {
// 由于类初始化顺序问题，不能使用Arrays.copyOf
char result[] = new char[value.length];
System.arraycopy(value, 0, result, 0, value.length);
return result;
}
这段代码取自openjdk的实现。我们尝试迭代字符串的每个元素，并将其复制到数组的每个单元格中。
迭代次数将等于字符串的长度。
英文:
Its O(N)
public char[] toCharArray() {
// Cannot use Arrays.copyOf because of class initialization order issues
char result[] = new char[value.length];
System.arraycopy(value, 0, result, 0, value.length);
return result;
}
This code is taken from openjdk implementation. We are trying to iterate each element of string and copy it into the each cell of array.
Number of iteration will be length of string.
答案4
得分: 0
根据官方Java文档，toCharArray()方法会创建一个新分配的字符数组，其长度为给定字符串的长度，并且其内容被初始化为包含给定字符串所表示的字符序列。由于它将每个字符从字符串复制到字符数组中，因此它需要线性时间，因此时间复杂度为O(n)，空间复杂度也为O(n)。
英文:
As per Official java doc toCharArray() creates a newly allocated character array whose length is the length of a given string and whose contents are initialized to contain the character sequence represented by the given string. As it's copying each character from string to char array it takes linear time, so Time complexity is O(n), and space complexity is also O(n).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论