Выбор алгоритма - понимание того, что и почему

Question

Я пишу документ и не был уверен в следующем:

1. Я собираюсь сравнить два алгоритма, которые могут работать на одной и той же структуре, но мы не можем сказать, что один всегда будет быстрее другого (и я определю обстоятельства, в которых a лучше, чем b, и наоборот); для этого я собирался использовать быструю сортировку и пузырьковую сортировку. Это хороший выбор?

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

Что вы думаете об алгоритмах, которые я выбрал для объяснения этих моментов, они кажутся уместными?

Спасибо всем!

Answer 1

1)

Сравнение быстрой сортировки и сортировки пузырьков, вероятно, не очень хорошая идея. пузырьковая сортировка даже не может превзойти быструю сортировку в небольших случаях.

хотя бы попробуйте быструю сортировку и вставку.

Я хотел бы попробовать алгоритмы минимального связующего дерева Прима и Крускала, чтобы показать силу и слабость двух алгоритмов на плотных и разреженных графах.

2) Сравнение бинарного и линейного поиска - хороший пример.

Answer 2

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

Answer 3

Это сильно зависит от точного назначения. Оба приведенных вами случая кажутся слишком очевидными.

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

Answer 4

Нет, потому что быстрая сортировка явно лучше, чем пузырьковая сортировка во всех случаях, за исключением очень небольшого набора обстоятельств, связанных с очень маленькими наборами данных.

Быстрая сортировка - это алгоритм O (n log n). Пузырьковая сортировка - это алгоритм O (n ² ).

Выберите один из других видов O (n log n), например сортировку слиянием или сортировку кучи.

Или сравните пузырьковую сортировку с сортировкой выбора или вставкой, оба O (n ² ).

Answer 5

Для (1) я бы предложил древовидную карту с O (Log N) доступом к Hashmap (O (1) доступом).

Кажется, что базовое «О» явно любимое хэш-карту, но потом:

• дерево связано логом N, тогда как наихудший случай для Hashmap - O (N) - когда все попадает в одну корзину
• дерево органично растет, чтобы вместить любое количество элементов. Hashmap становится неэффективным с плохим соотношением nItems / nBuckets, в этом случае вам придется перефразировать

Есть еще несколько вещей, которые вы могли бы выяснить ...:)

Answer 6

Обычный способ сравнения алгоритмов - использование Big-O-нотации (нотация Ландау) для описания ограничивающего поведения функции.

Только в (очень) краткое:

Предположим, у вас есть функция, которая принимает n элементов (алгоритм сортировки: размер вашей коллекции). Теперь мы смотрим на алгоритм и пытаемся выяснить, какое максимальное количество «шагов» (связанных с n ) необходимо завершить.

Некоторые алгоритмы завершаются в постоянное время (чтение Hashtable), которое составляет O(1). Если у вас есть алгоритм, который должен «смотреть» на каждый элемент один раз, это O(n) (линейный), если вам нужно посмотреть на него дважды, то это O(2n) (все еще линейный). Ссылка, которую я предоставил, содержит больше примеров.

Для распространенных алгоритмов O-обозначения хорошо известны. Но это не так уж сложно проанализировать существующий алгоритм. (Реальная задача состоит в том, чтобы придумать алгоритм для данной задачи, который быстрее, чем уже известное;))

Answer 7

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

В Википедии много полезной информации о алгоритмах сортировки , внимательно прочитайте и изучите.

Наиболее важными аспектами для сравнения алгоритмов являются сложность вычислений и использование памяти; см. также анализ алгоритмов .