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

Question

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

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

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

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

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

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

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

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

И я предполагаю, что это было бы:

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

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

7

php algorithm

задан Bill the Lizard 29 May 2013 в 21:52

3 ответа

Другие вопросы по тегам:

php algorithm

Похожие вопросы:

score 2 · 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 , который потребует либо 1 операцию (найденную как первый элемент) до длины 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

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

score 0 · Answer 2

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

score 1 · Answer 3

Нотация Big O - это приближения. Это упрощает сравнение алгоритмов.

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

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

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

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

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

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

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

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