Как вложенное в то время как l oop может быть O (n)? - PullRequest
Новая
       21

Как вложенное в то время как l oop может быть O (n)?

1 голос
/ 21 апреля 2020

У меня есть этот код здесь с сайта www.interviewcake.com, который на сайте называется O (n), и после запроса разъяснения у члена команды на собеседовании они подтвердили, что это правда. Вот код: 

function reverseWords(message) {

  // First we reverse all the characters in the entire message
  reverseCharacters(message, 0, message.length - 1);
  // This gives us the right word order
  // but with each word backward

  // Now we'll make the words forward again
  // by reversing each word's characters

  // We hold the index of the *start* of the current word
  // as we look for the *end* of the current word
  let currentWordStartIndex = 0;
  for (let i = 0; i <= message.length; i++) {

    // Found the end of the current word!
    if (i === message.length || message[i] === ' ') {

      // If we haven't exhausted the string our
      // next word's start is one character ahead
      reverseCharacters(message, currentWordStartIndex, i - 1);
      currentWordStartIndex = i + 1;
    }
  }
}

function reverseCharacters(message, leftIndex, rightIndex) {

  // Walk towards the middle, from both sides
  while (leftIndex < rightIndex) {

    // Swap the left char and right char
    const temp = message[leftIndex];
    message[leftIndex] = message[rightIndex];
    message[rightIndex] = temp;
    leftIndex++;
    rightIndex--;
  }
}

Объяснение того, что член команды на собеседовании сказал следующее:

* Да, есть вложенный l oop, который делает его похожим на O (n ^ 2).

Но, по ходу проблемы, мы видим, что мы не обращаем O (n) символов в каждом внутреннем l oop ... мы только обращаем вспять каждый символ ровно в два раза Таким образом, общая стоимость в конечном итоге становится O (n).

Это сложная задача, потому что вы должны смотреть на стоимость всех обращений к reverseCharacters по всему алгоритму, а не каждый вызов на его собственный. *

Я все еще в замешательстве, поскольку мы все еще перебираем КАЖДЫЙ символ во внутреннем l oop, и чем больше строка, тем больше времени потребуется для выполнения вызова.

Я хотел открыть это для другого канала и посмотреть, смогу ли я получить дополнительную информацию об этом и почему его O (n) вместо O (n) ^ 2.

Для чтобы быть совершенно ясным, я хотел бы объяснить, почему функция reverseWords в приведенном выше коде является O (n), а не O (n) ^ 2

Ответы [ 2 ]

3 голосов
/ 21 апреля 2020

Из того, что я могу сказать в этом коде, внешняя работа l oop заключается в поиске конца каждого слова. Как только кто-то найден (и только потом), вызывается reverseCharacters(), чтобы поменять символы в этом слове. Таким образом, большая O из двух задач складывается вместе (O (n) + O (n) = O (2n), которая все еще считается O (n)), а не умножается вместе (O (n) * O (n) = O (n ^ 2)), как и следовало ожидать от них во вложенных циклах.

0 голосов
/ 22 апреля 2020

Это действительно O(n).

Путаница возникает из-за того, что reverseCharacters() вызывается во внутреннем l oop. Но обратите внимание, КОГДА это вызывается.

Давайте посмотрим на какой-нибудь произвольный символ в строке и посмотрим, как часто он "затрагивается". Пусть наш символ будет с индексом i для некоторых i.

reverseCharacters() во внутренней l oop, вызывается один раз для каждого слова во входной строке. Символ i появляется ровно в одном слове.

Это означает, что фактическая сложность этого кода: 

T(n) = O(n       //    First reverseCharacters()
         +  n    // looping through all characters
         + l1    // reverseCharacters() on the first word
         + l2    // reverseCharacters() on the second word
         + ...   // and so on ...
         + lk)   // reverseCharacters() on the k'th (and last) word.

Поскольку l1 + l2 + ... + lk <= n, это означает, что мы имеем: 

T(n) = O(n + n + l1 + l2 + ... + lk) <= O(n + n + n) = O(n)
...