Проводим ли мы анализ алгоритмов на основе модели вычислений или на основе «здравого смысла»? - PullRequest
Новая
       35

Проводим ли мы анализ алгоритмов на основе модели вычислений или на основе «здравого смысла»?

0 голосов
/ 12 июня 2018

Недавно я читал эти книги об алгоритмах, в частности, раздел об анализе алгоритмов:

  • Введение в алгоритмы.3-е изд.TCRC
  • Руководство по разработке алгоритма.2-е изд.С. Шиена
  • Разработка алгоритма.J.Kleinberg & Eva Tardos
  • Алгоритмы.4-е изд.Р. Седжвик
  • Алгоритмы.С. Дасгупта, С. Пападимитриу и Вазирани
  • несколько других книг

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

Я имею в виду, во Введении к Алгоритмам и Руководству по проектированию алгоритмов упоминается то, что называется моделью вычисления RAM.В этих книгах говорится, что согласно этой модели мы считаем шаги, но в других книгах модель вычисления как таковая не упоминается.

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

Какая связь (или разница) между методом подсчета шагов (другие книги) и использованием модели вычислений (TCRC & S. Skiena)сделать это?Когда кто-то говорит о подсчете шагов для анализа алгоритмов, могу ли я предположить, что он имеет в виду использование модели вычислений (RAM)?

1 Ответ

0 голосов
/ 12 июня 2018

Наш здравый смысл основан на модели вычислений, которая может быть неявной или явной.Обычно в вводном курсе это неявно.Явно, что вы обычно используете модель RAM.Который основан на идее последовательной обработки, где каждая простая операция занимает постоянное время.Таким образом, вы просто подсчитываете шаги.

Формальное описание этой модели вы можете найти на http://people.seas.harvard.edu/~cs125/fall14/lec6.pdf.

Реальность, конечно, несколько иная.Как показывает https://gist.github.com/jboner/2841832, операции занимают огромное количество времени.Лично я видел, как работа от 5 дней до 1 часа переключалась на использование сортировки вместо поиска хешей.Да, поиск по хешу O(1), но с ужасной константой, когда данные сохраняются на диске.Распределенные вычисления работают параллельно.Вычисления на графическом процессоре дают вам огромное количество параллелизма ... при условии, что все вычисления работают в идеальном режиме.Мы пытаемся создать квантовые компьютеры, которые теоретически могут дать нам много, много порядков большего параллелизма ... за счет потери необратимых операций, таких как "если".

Мы можем создавать модели, которые имеют дело свся эта сложность.Но нет необходимости рассматривать что-либо из этого, пока вы не поймете основы.Что является стандартной функцией «подсчета операций» в модели RAM.

...