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

Question

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

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

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

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

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

Answer 1

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

Quicksort - это алгоритм O (n log n). Bubble sort - это алгоритм O (n).

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

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

Answer 2

1)

сравнения и быстрой сортировки BubbleSort, вероятно, не является хорошей идеей. bubblesort даже не может бить quicksort в небольших случаях.

по крайней мере, попробуйте quicksort и insertsort.

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

2) Сравнение двоичного поиска и линейного поиска является хорошим примером здесь.

Answer 3

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

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

Answer 4

Изучение quicksort и bubble sort и найти ответ - возможно, в некоторых случаях он лучше другого.

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

Наиболее важные аспекты для сравнения алгоритмов: computational complexity и использование памяти; см. также analysis of algorithms.

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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

Основной «O», кажется, явно любимый HashMap, но потом:

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

Есть несколько других вещей, xyou мог понять ... :)