Имеет ли этот алгоритм временную сложность O (n) или O (n ^ 2)? - PullRequest
Новая
       7

Имеет ли этот алгоритм временную сложность O (n) или O (n ^ 2)?

3 голосов
/ 20 января 2020 
  public static void reverseWords(char[] message) {
    reverseCharacters(message, 0, message.length - 1);
    int currentWordStartIndex = 0;
    for (int i = 0; i <= message.length; i++) {
        if (i == message.length || message[i] == ' ') {
            reverseCharacters(message, currentWordStartIndex, i - 1);
            currentWordStartIndex = i + 1;
        }
    }
}

private static void reverseCharacters(char[] message, int leftIndex, int rightIndex) {
    while (leftIndex < rightIndex) {
        char temp = message[leftIndex];
        message[leftIndex] = message[rightIndex];
        message[rightIndex] = temp;
        leftIndex++;
        rightIndex--;
    }
}

На первый взгляд кажется, что это будет иметь временную сложность O (n) и пространственную сложность O (1). Это также предлагается автором. Однако функция reverseWords сначала вызывает reverseCharacters, который имеет временную сложность O (n) и пространственную сложность O (1).

Затем for для l oop, который будет работать максимум из n раз, и он вызывает reverseCharacters опять же, который содержит время l oop, которое также будет запускаться n раз. Разве это не означает, что сложность по времени будет O (n ^ 2)?

Был ли код из вспомогательной функции фактически включен в функцию reverseWord, изменяет ли он сложность пространства или времени?

1 Ответ

3 голосов
/ 20 января 2020

[..] для l oop, который будет работать не более n раз

True

[..] и вызывает reverseCharacters снова, который содержит некоторое время l oop, которое также будет запускаться n раз.

Это не так.

reverseCharacters вызывается, когда reverseWords встречается с пробелом или конец строки Границы leftIndex и rightIndex указывают на начало и конец слова и не перебирают всю строку.

Таким образом, каждый символ в строке отображается дважды, что похоже на O(n + n), что is O(n).

Пример:

Для строки abcd efg hijk очевидно, что reverseWords сканирует эту строку.

Когда он видит пробел или конец строки, он вызывает reverseCharacters. Это происходит три раза для приведенной выше строки - от (a - d), (e - g) и (h - k). Это меняет символы между границами. Каждая из этих операций не O(n).

...