Big O Notation для пространственной сложности преобразования строки в массив символов

Question

Задана строка String str = "absdf"; длины N и если мы преобразуем ту же строку в char Array, используя - char [] arr = str.toCharArray ();.

Считается ли это дополнительным пробелом O (N), или будет O (1)?

Answer 1

Это O(N), как предлагает @andy, реализация String.toCharArray() выглядит примерно так:

public char[] toCharArray() {
  char result[] = new char[value.length];
  // copy the contents
  return result;
}

Answer 2

Его 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;
}

Этот код взят из реализации openjdk. Мы пытаемся перебрать каждый элемент строки и скопировать его в каждую ячейку массива. Количество итераций будет равно длине строки.

Answer 3

Сложность времени будет O(N). Аналогично созданию нового массива, равного длине строки, и копированию строки в массив символов. Создание массива занимает O(N) времени, а копирование - O(N). Таким образом, общая сложность в худшем случае будет O(N).