Анализ алгоритма - обозначение Big O - PullRequest
Новая
       3

Анализ алгоритма - обозначение Big O

0 голосов
/ 14 декабря 2010

Какая хорошая стратегия для определения времени работы (обозначение Big O) структур данных и алгоритмов.У меня есть следующее, чтобы выяснить время работы, и у меня возникают проблемы с определением, что это будет.

AINC - это массив, содержащий n целых чисел, расположенных в порядке возрастания.

AD - массив, содержащий n целых чисел, расположенных в порядке убывания.

AR - массив, содержащий n целых чисел вслучайный порядок.

Q - это очередь, реализованная в виде связанного списка и содержащая p элементов.

LINK - это связанный список, содержащий n узлов.

CIRC - круговой связанный списоксодержащий n элементов, где C указывает на последний элемент.

T - это двоичное дерево поиска, содержащее n узлов.

a) Поиск элемента в AINC с использованием линейного поиска.

б) Удаление 10-го узла связанного списка LINK.

c) Вызов функции, которая использует Q, и вызывает dequeue m раз.

d) Вставка элемента в конец списка CIRC.

e) Удаление последнего элемента CIRC.

f) Нахождение наибольшего элемента T.

g) Определение высоты T.

h) Выбор сортировки вызовов (AINC, n).

i) Делать два звонка один за другим.Первый вызов - это сортировка слиянием (AD, n), за которой следует сортировка вставок вызовов (AD, n).

j) Преобразование десятичного целого числа num в его двоичный эквивалент.

*** Это не hw.Я готовлюсь к экзамену.

Ответы [ 2 ]

2 голосов
/ 14 декабря 2010

Если вы новичок в анализе Big O и у вас есть время (2,5 часа), я бы порекомендовал посмотреть первые две лекции этого класса алгоритмов, прочитанные самим Лизерсоном.

2 голосов
/ 14 декабря 2010

(так как ОП попросил его)

Вы берете лист бумаги.

  • Если в вашем вопросе упоминается число (например, повторите n раз или найдите n -й последний элемент):

Вы вручную выполняете на бумаге операции, необходимые для выполнения упомянутого действия, когда это число равно 1 (если применимо).

Вы повторяете для каждого из следующих значений этого числа: 2, 10, 20, 100, 1000 и 10000. Просто для ударов вы также можете попробовать с фактическим числом, упомянутым в вопросе.

Вы измеряете время, которое вам потребовалось для каждого случая, а затем вы наносите на лист бумаги (а, может быть, электронная таблица также будет выполнять) функцию t(n), где t - время, а n номер.

Вы просматриваете свои старые математические книги, чтобы определить кривую. Например. если это парабол, скорее всего, у вас в руках алгоритм O (n ^ 2).

  • Если в вашем вопросе не указан номер:

Повторите предыдущую процедуру, используя 2, 10, 20, 100, 1000 и 10000 элементов в любой упомянутой структуре данных (массив, список и т. Д.). Если «структура» - это число, просто используйте столько цифр.

Примечание:

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

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

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

EDIT:

Поиск по algorithms and complexity в Google также дает целую кучу интересных результатов. Вы должны попробовать это время от времени ...

...