Блог

Главная - Вопросы по программированию - Выполняет ли метод .includes в JavaScript цикл по массиву и регистру O (n)?

Выполняет ли метод .includes в JavaScript цикл по массиву и регистру O (n)?

#javascript #algorithm #loops #methods

#javascript #алгоритм #циклы #методы

Вопрос:

Вызывает ли метод .includes O (n ^ 2) при запуске с другим циклом, таким как в этом простом примере?

 function myFn(){
    let age = people.map(person => {
            if(person > 21){
              return "YES";
        } else {
          return "NO";
        }
    return age.includes('NO') ? 'NO' : 'YES';
}

Комментарии:

1. В худшем случае он должен проверять каждый элемент в массиве. Так что да, myFn сложность n^2

2. Я пытался сделать это без второго цикла, и мне было просто любопытно посмотреть, вызывает ли включение цикл.

3. Как еще он будет проверять каждый элемент в коллекции?

4. @JeromeCode попробуйте return people.some(age => age < 21) ? 'NO' : 'YES'

5. Я не знал, вызовет ли это O (^ n) при запуске с другим циклом.

Ответ №1:

Метод указан таким образом, что он действительно проходит через массив элемент за элементом. Итак, это O (n) (линейный). Но это после вашего map , который уже прошел весь путь через массив.

Реализации движка JavaScript бесплатны (как всегда) для оптимизации при условии, что оптимизация не изменяет семантику метода.

Однако, если вы хотите просмотреть массив в поисках элемента, соответствующего произвольному условию, map includes — не лучший выбор; some и every лучше, потому что они замыкают цикл (останавливают цикл), когда находят элемент, который проходит ( some ) или не проходит ( every ) тест. Ваш код проверяет, есть ли каждый элемент в people > 21 , так что это будет:

 function myFn() {
    return people.every(person => person > 21) ? "YES" : "NO";
}