Блог

Главная - Вопросы по программированию - Большое обозначение O для функции js для проверки подмножества

Большое обозначение O для функции js для проверки подмножества

#big-o

Вопрос:

я написал функцию, которая проверяет подмножество массива. Для обозначения большого числа, как объяснить эту функцию? это просто O(n) для этой функции?

 function isSubset(arr1, arr2) {
  return arr2.filter(function(e) { return arr1.indexOf(e) < 0 })==0;
}

isSubset(['A','B','C','D','E'],['A','D','Z'])  -> false

isSubset(['A','B','C','D','E'],['A','E','D']) -> true

Ответ №1:

Существует 4 правила для классификации 0(n).

Правило 1: Всегда наихудший случай.

Правило 2: Удалите Константы.

Правило 3: Разные входные данные должны иметь разные переменные.

   1. ( ) for steps in order.

  2. (*) for nested steps.

Правило 4: Отбросьте недоминирующие термины.

Таким образом, два массива во входных данных имеют разные размеры. Итак, согласно правилу 3, ваша временная сложность будет 0(n*m) .

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

1. немного смущен, что это n^m? фильтр с индексом . В этом случае набор вопросов ([«A», «B», «C», «D», «E»], [«A», «D», «Z»]) фильтр будет циклически повторяться 5 раз, каждый раз будет индексироваться, означает ли это 3 раза?

2. Видите, теперь у вас первый размер массива равен 5, а 2-й-3, так что он будет выполняться 15 раз. Но предположим, что у вас есть массив из 10000 x 15000 элементов. Всегда думайте о производительности своего кода в худшем случае и реорганизуйте код, чтобы стать лучшим программистом. Посмотрите на производительность кода в соответствии со сложностями по этой ссылке bigocheatsheet.com . Производительность вашего кода в худшем случае будет ужасной.

3. Большое спасибо, теперь я все понял. еще один вопрос, если эту функцию выполнять как рефакторинг, как ее улучшить?

4. Сначала вы можете сохранить значения подмножества в одном массиве или списке. Затем вы можете использовать другой цикл, чтобы проверить, присутствует ли значение в массиве или нет. Тогда временная сложность кода будет 0(a b) намного выше, чем 0(a*b) . Если вам понравился мой ответ, я буду признателен, если вы поддержите мой ответ.

5. могу ли я привести пример, не знаю, как перейти на a b

Ответ №2:

filter Функция Javascript будет перебирать все элементы, поэтому ее сложность такова O(n) . Найдите прототип функции здесь Массив.прототип.фильтр

При повторении каждого элемента в filter вы используете indexOf функцию, которая также повторяет все элементы во втором массиве, пока не найдет соответствующий символ, поэтому ее сложность также O(m) . Найдите прототип функции здесь Array.prototype.indexOf

Как indexOf вложено, так и его сложность будет умножена на filter сложность, которая O(n*m)

Так isSubset что сложность будет O(n*m)

Метки: