Как определить лучший и худший варианты программы (алгоритма)?

Question

Предположим, у меня есть эта программа, я хочу сравнить 2 списка ввода. Предположим, массив A и массив B. Как определить наилучший и наихудший случай функции?

Вот мой код в [php]:

foreach($array_1 as $k){
    if(!in_array($k, $array_2)){
        array_push($array_2, $k);
    }
}   

Каков наилучший и наихудший случай цикла for? Пожалуйста, включите некоторые объяснения, спасибо:)

РЕДАКТИРОВАНИЕ:

Поскольку моя цель состоит в том, чтобы сравнить 2 списка, которые имеют в списках 1 общий элемент. Я думаю, что мой приведенный выше код неверен. Вот обновленный мой код

foreach($array_1 as $k){
    if(in_array($k, $array_2)){
        array_push($array_3, $k);
    }
}

И я думаю, это будет:

Лучший случай: O (n)

Худший случай: O (N * M)

Answer 1

Давайте сделаем быстрый анализ:

foreach($array_1 as $k)

означает, что операция внутри будет повторяться для каждого элемента массива. Позвольте обозначить размер массива N.

Операция в пределах:

if (!in_array($k, $array_2)) {
  array_push($array_2, $k);
}

Здесь есть 2 операции:

• in_array
• array_push

array_push, вероятно, будет постоянным, таким образом, O(1), тогда как in_array, скорее, линейный поиск в array_2, который займет одну операцию (найденную как первый элемент) вплоть до длины array_2 операции.

Обратите внимание, что in_array представляет единственную переменную здесь:

• лучший случай: in_array возвращает при первом сравнении -> все элементы array_1 одинаковы, либо либо array_2 было пустым, либо они равны его первому элементу. Сложность O(N), так как у нас N элементов в array_1
• худший случай: каждый раз, когда мы проверяем каждый элемент array_2 ->, все элементы array_1 отличаются и отличаются от предыдущих элементов array_2. Если M - это длина array_2, когда она вводится, то сложность идет по линии O(N * (N+M) ), (N+M)/2 - это среднее время поиска в array_2, поскольку оно увеличивается с M до M+N элементов и константа 2 отбрасывается в нотации O

Надеюсь, это поможет.

Answer 2

Обозначение Big O все о приближениях. Это облегчает сравнение алгоритмов.

Если вы представляете свой массив элементов, поиск может иметь порядок N (вы должны просмотреть каждый элемент, чтобы найти нужный элемент), это может быть порядок Log (N), если у вас есть упорядоченная коллекция, или он может даже заказ 1 в зависимости от типа вашей коллекции.

Здесь важно посмотреть на ваш алгоритм и определить, какие ключевые операции повторяются.

Foreach, безусловно, является операцией порядка N, по определению вы должны оперировать каждым элементом в вашем списке. O (N)

Следующим является ваш if InArray 2. Это звучит как поиск по массиву, который, скорее всего, будет неупорядоченным, так что это будет порядок N (линейный поиск). Таким образом, ваша сложность теперь будет O (N * M). (для каждого n элементов в массиве 1 выполните поиск порядка N по массиву 2).

Наконец, у вас есть толчок массива. Я не знаю вашу среду, но это может быть порядок 1 или порядок N, если массив необходимо перераспределить и скопировать для роста. Примем порядок 1 для простоты. Следовательно, ваша сложность в Большой О равна O (N * M).

Так что теперь лучше всего, чтобы каждый элемент нашел свою копию с первой попытки и выполнил толчок массива, который был бы O (N * 1 * 1) = O (N).

В худшем случае каждый элемент не может быть найден во втором списке, что приводит к полному поиску всех элементов в массиве 2. Следовательно, сложность равна O (N * M).

Ваши учителя хотят понять ваше мышление, поэтому покажите им свои предположения. Я настоятельно рекомендую вам прочитать точный вопрос и информацию, которую вы получили, прежде чем полагаться на приведенные здесь предположения. Возможно, вам сообщили язык / платформу, в которой указывалось бы точное наказание и алгоритмы, используемые в каждом случае. Надеюсь, это поможет:)

Answer 3

Как правило, с такой проблемой я просто смотрю на алгоритм «Доктор Зло» и спрашиваю: «Как сделать так, чтобы это заняло самое возможное время?"