Jump to content

Анализ алгоритмов

(Перенаправлено с Размера проблемы )
Для поиска заданной записи в заданном упорядоченном списке как двоичный , так и алгоритм линейного поиска можно использовать (который игнорирует порядок). Анализ первого и второго алгоритма показывает, что требуется не более log 2 n и n для списка размера n шагов проверки соответственно . В приведенном примере списка размером 33 поиск «Морен, Артур» занимает 5 и 28 шагов в двоичном формате (показано на рисунке). голубой ) и линейный ( пурпурный ) поиск соответственно.
Графики функций, обычно используемых при анализе алгоритмов, показывающие количество операций N в зависимости от размера входных данных n для каждой функции.

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

Термин «анализ алгоритмов» был придуман Дональдом Кнутом . [1] Анализ алгоритмов является важной частью более широкой теории сложности вычислений , которая обеспечивает теоретические оценки ресурсов, необходимых для любого алгоритма, решающего данную вычислительную задачу . Эти оценки дают представление о разумных направлениях поиска эффективных алгоритмов .

При теоретическом анализе алгоритмов принято оценивать их сложность в асимптотическом смысле, т. е. оценивать функцию сложности для сколь угодно больших входных данных. обозначения Big O , обозначения Big-omega и обозначения Big-theta . Для этой цели используются [2] Например, говорят, что двоичный поиск выполняется за несколько шагов, пропорциональных логарифму размера n искомого отсортированного списка или за O (log n ) , что в просторечии «за логарифмическое время ». Обычно асимптотические используются оценки, поскольку разные реализации одного и того же алгоритма могут различаться по эффективности. Однако эффективность любых двух «разумных» реализаций данного алгоритма связана постоянным мультипликативным коэффициентом, называемым скрытой константой .

Точные (не асимптотические) показатели эффективности иногда можно вычислить, но обычно они требуют определенных предположений относительно конкретной реализации алгоритма, называемой моделью вычислений . Модель вычислений может быть определена в терминах абстрактного компьютера , например, машины Тьюринга , и/или путем постулирования того, что определенные операции выполняются в единицу времени.Например, если отсортированный список, к которому мы применяем двоичный поиск, имеет n элементов, и мы можем гарантировать, что каждый поиск элемента в списке может быть выполнен за единицу времени, то не более log 2 ( n ) + 1 единиц времени будет необходимо вернуть ответ.

Модели затрат

[ редактировать ]

Оценки эффективности использования времени зависят от того, что мы определяем как шаг. Чтобы анализ эффективно соответствовал реальному времени выполнения, время, необходимое для выполнения шага, должно быть гарантированно ограничено константой сверху. Здесь нужно быть осторожным; например, в некоторых анализах сложение двух чисел считается одним шагом. Это предположение может не быть оправданным в определенных контекстах. Например, если числа, участвующие в вычислении, могут быть сколь угодно большими, время, необходимое для одного сложения, больше нельзя считать постоянным.

Обычно используются две модели затрат: [3] [4] [5] [6] [7]

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

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

Ключевой момент, который часто упускают из виду, заключается в том, что опубликованные нижние оценки задач часто даются для модели вычислений, которая более ограничена, чем набор операций, которые вы могли бы использовать на практике, и поэтому существуют алгоритмы, которые быстрее, чем те, которые наивно можно было бы считать. думал возможно. [8]

Анализ времени выполнения

[ редактировать ]

Анализ времени выполнения — это теоретическая классификация, которая оценивает и прогнозирует увеличение времени работы (или времени выполнения или времени выполнения) алгоритма по мере увеличения его входного размера (обычно обозначаемого как n ). Эффективность выполнения — это тема, представляющая большой интерес в информатике : программы выполнение может занять секунды, часы или даже годы, в зависимости от того, какой алгоритм она реализует. Хотя методы программного профилирования можно использовать для измерения времени выполнения алгоритма на практике, они не могут предоставить данные о времени для всех бесконечно многих возможных входных данных; последнее может быть достигнуто только теоретическими методами динамического анализа.

Недостатки эмпирических метрик

[ редактировать ]

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

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

n (размер списка) Компьютер
наносекундах )
Время выполнения компьютера B
наносекундах )
16 8 100,000
63 32 150,000
250 125 200,000
1,000 500 250,000

Основываясь на этих показателях, было бы легко прийти к выводу, что компьютер A использует алгоритм, который по эффективности намного превосходит алгоритм B. компьютера Однако если размер входного списка увеличиться до достаточного числа, этот вывод окажется ошибочным:

n (размер списка) Компьютер
наносекундах )
Время выполнения компьютера B
наносекундах )
16 8 100,000
63 32 150,000
250 125 200,000
1,000 500 250,000
... ... ...
1,000,000 500,000 500,000
4,000,000 2,000,000 550,000
16,000,000 8,000,000 600,000
... ... ...
63,072 × 10 12 31,536 × 10 12 нс,
или 1 год
1 375 000 нс,
или 1,375 миллисекунды

Компьютер А, на котором запущена программа линейного поиска, демонстрирует линейную скорость роста. Время выполнения программы прямо пропорционально размеру входных данных. Удвоение размера ввода удваивает время выполнения, увеличение размера ввода в четыре раза увеличивает время выполнения в четыре раза и так далее. С другой стороны, компьютер B, на котором запущена программа двоичного поиска, демонстрирует логарифмическую скорость роста. Увеличение входного размера в четыре раза увеличивает время выполнения только на постоянную величину (в данном примере 50 000 нс). Несмотря на то, что компьютер A якобы является более быстрой машиной, компьютер B неизбежно превзойдет компьютер A во время выполнения, поскольку он использует алгоритм с гораздо более медленной скоростью роста.

Порядки роста

[ редактировать ]

Неформально можно сказать, что алгоритм демонстрирует скорость роста порядка математической функции , если за пределами определенного входного размера n функция f ( n ) , умноженная на положительную константу, обеспечивает верхнюю границу или предел времени выполнения этого алгоритма. алгоритм. Другими словами, для заданного входного размера n, большего некоторого n 0 и константы c , время выполнения этого алгоритма никогда не будет больше, чем c × f ( n ) . Эта концепция часто выражается с использованием обозначения Big O. Например, поскольку время выполнения сортировки вставкой растет квадратично по мере увеличения входного размера, можно сказать, что сортировка вставкой имеет порядок O ( n 2 ) .

Обозначение Big O — удобный способ выразить наихудший сценарий для данного алгоритма, хотя его также можно использовать для выражения среднего случая — например, наихудший сценарий для быстрой сортировки — это O ( n 2 ) , но среднее время выполнения составляет O ( n log n ) .

Эмпирические порядки роста

[ редактировать ]

Предполагая, что время выполнения соответствует правилу степени, t kn а , коэффициент a можно найти [9] путем проведения эмпирических измерений времени выполнения { t 1 , t 2 } в некоторых точках размера проблемы { n 1 , n 2 } и вычисления t 2 / t 1 = ( n 2 / n 1 ) а так что a = log( t 2 / t 1 )/log ( n 2 / n 1 ) . Другими словами, это измеряет наклон эмпирической линии на логарифмическом графике зависимости времени выполнения от размера входных данных в некоторой точке размера. Если порядок роста действительно соответствует степенному правилу (и поэтому линия на логарифмическом графике действительно является прямой линией), эмпирическое значение будет оставаться постоянным в разных диапазонах, а если нет, то оно будет меняться (и линия представляет собой изогнутую линию), но все же может служить для сравнения любых двух заданных алгоритмов относительно их эмпирических локальных порядков поведения роста. Применительно к приведенной выше таблице:

n (размер списка) Компьютер
наносекундах )
Локальный порядок роста
(н^_)
Время выполнения компьютера B
наносекундах )
Локальный порядок роста
(н^_)
15 7 100,000
65 32 1.04 150,000 0.28
250 125 1.01 200,000 0.21
1,000 500 1.00 250,000 0.16
... ... ...
1,000,000 500,000 1.00 500,000 0.10
4,000,000 2,000,000 1.00 550,000 0.07
16,000,000 8,000,000 1.00 600,000 0.06
... ... ...

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

Оценка сложности во время выполнения

[ редактировать ]

Сложность во время выполнения для наихудшего сценария данного алгоритма иногда можно оценить, исследовав структуру алгоритма и сделав некоторые упрощающие предположения. Рассмотрим следующий псевдокод :

1    get a positive integer n from input2    if n > 103        print "This might take a while..."4    for i = 1 to n5        for j = 1 to i6            print i * j7    print "Done!"

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

В приведенном выше алгоритме шаги 1, 2 и 7 выполняются только один раз. Для оценки наихудшего случая следует предположить, что также будет выполнен шаг 3. Таким образом, общее время выполнения шагов 1–3 и шага 7 составит:

Циклы на шагах 4, 5 и 6 сложнее оценить. Тест внешнего цикла на шаге 4 будет выполнен ( n + 1 ).раз, [10] что потребует времени T 4 ( n + 1 ). С другой стороны, внутренний цикл управляется значением j, которое повторяется от 1 до i . При первом проходе внешнего цикла j выполняет итерацию от 1 до 1: внутренний цикл выполняет один проход, поэтому выполнение тела внутреннего цикла (шаг 6) занимает время T 6 , а проверка внутреннего цикла (шаг 5) занимает 2 T. 5 раз. Во время следующего прохода внешнего цикла j выполняет итерацию от 1 до 2: внутренний цикл делает два прохода, поэтому выполнение тела внутреннего цикла (шаг 6) занимает 2 T 6 времени, а проверка внутреннего цикла (шаг 5) занимает 3 Т 5 раз.

В целом общее время, необходимое для выполнения тела внутреннего цикла , можно выразить в виде арифметической прогрессии :

который можно факторизовать [11] как

Общее время, необходимое для выполнения теста внутреннего цикла, можно оценить аналогично:

который можно расценивать как

Таким образом, общее время работы этого алгоритма составит:

что сводится к

Как правило , можно предположить, что член высшего порядка в любой заданной функции доминирует над скоростью ее роста и, таким образом, определяет ее порядок во время выполнения. В этом примере н 2 является членом высшего порядка, поэтому можно заключить, что f ( n ) = O ( n 2 ) . Формально это можно доказать следующим образом:

Докажите, что





Пусть k — константа, большая или равная [ T 1 .. T 7 ]



Поэтому

Более элегантный подход к анализу этого алгоритма состоял бы в том, чтобы объявить, что все [ T 1 .. T 7 ] равны одной единице времени в системе единиц, выбранной так, чтобы одна единица была больше или равна фактическому времени для эти шаги. Это будет означать, что время выполнения алгоритма разбивается следующим образом: [12]

Анализ темпов роста других ресурсов

[ редактировать ]

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

while file is still open:    let n = size of file    for every 100,000 kilobytes of increase in file size        double the amount of memory reserved

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

Актуальность

[ редактировать ]

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

Постоянные факторы

[ редактировать ]

Анализ алгоритмов обычно фокусируется на асимптотической производительности, особенно на элементарном уровне, но в практических приложениях важны постоянные факторы, а размер реальных данных на практике всегда ограничен. Обычно ограничением является размер адресуемой памяти, поэтому на 32-битных машинах 2 32 = 4 ГиБ (больше, если сегментированная память ) и на 64-битных машинах 2 используется 64 = 16 ЭйБ. Таким образом, при ограниченном размере порядок роста (времени или пространства) может быть заменен постоянным коэффициентом, и в этом смысле все практические алгоритмы равны O (1) для достаточно большой константы или для достаточно малых данных.

Эта интерпретация в первую очередь полезна для функций, которые растут очень медленно: (двоичный) повторный логарифм (log * ) меньше 5 для всех практических данных (2 65536 биты); (двоичный) log-log (log log n ) меньше 6 практически для всех практических данных (2 64 биты); двоичный журнал (log n ) меньше 64 практически для всех практических данных (2 64 биты). Тем не менее алгоритм с непостоянной сложностью может быть более эффективным, чем алгоритм с постоянной сложностью для практических данных, если накладные расходы алгоритма с постоянным временем приводят к большему постоянному коэффициенту, например, можно до тех пор, пока и .

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ «Кнут: Последние новости» . 28 августа 2016 г. Архивировано из оригинала 28 августа 2016 г.
  2. ^ Кормен, Томас Х., изд. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. стр. 44–52. ISBN  978-0-262-03384-8 . OCLC   311310321 .
  3. ^ Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Уллман (1974). Разработка и анализ компьютерных алгоритмов . Паб Аддисон-Уэсли. компании ISBN  9780201000290 . , раздел 1.3
  4. ^ Юрай Хромкович (2004). Теоретическая информатика: введение в автоматы, вычислимость, сложность, алгоритмика, рандомизация, связь и криптография . Спрингер. стр. 177–178. ISBN  978-3-540-14015-3 .
  5. ^ Джорджио Аузиелло (1999). Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации . Спрингер. стр. 3–8. ISBN  978-3-540-65431-5 .
  6. ^ Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов , Берлин, Нью-Йорк: Springer-Verlag , с. 20, ISBN  978-3-540-21045-0
  7. ^ Роберт Эндре Тарьян (1983). Структуры данных и сетевые алгоритмы . СИАМ. стр. 3–7. ISBN  978-0-89871-187-5 .
  8. ^ Примеры цены абстракции? , cstheory.stackexchange.com
  9. ^ Как избежать O-злоупотреблений и взяток. Архивировано 8 марта 2017 г. в Wayback Machine , в блоге «Потерянное письмо Гёделя и P = NP» Р. Дж. Липтона, профессора компьютерных наук Технологического института Джорджии, рассказывающего об идее Роберта Седжвика.
  10. ^ для завершения цикла for требуется дополнительный шаг, следовательно, n + 1, а не n выполнений
  11. ^ можно доказать, По индукции что
  12. ^ Этот подход, в отличие от описанного выше подхода, пренебрегает постоянным временем, затрачиваемым на тесты цикла, которые завершают соответствующие циклы, но тривиально. доказать, что такое упущение не влияет на конечный результат,
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3b4311a2678cc5387f27373e0cf546ec__1721569620
URL1:https://arc.ask3.ru/arc/aa/3b/ec/3b4311a2678cc5387f27373e0cf546ec.html
Заголовок, (Title) документа по адресу, URL1:
Analysis of algorithms - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)