Структуры данных и алгоритмы, страница 7

Поэтому, с финансовой точки зрения, более предпочтительным может статьсложный комплексный алгоритм (в надежде, что результирующая программа будетвыполняться существенно быстрее, чем более простая программа). Но и в этой ситуации разумнее сначала реализовать простой алгоритм, чтобы определить, как должнасебя вести более сложная программа. При построении сложной программной системыжелательно реализовать ее простой прототип, на котором можно провести необходимыеизмерения и смоделировать ее поведение в целом, прежде чем приступать к разработкеокончательного варианта. Таким образом, программисты должны быть осведомлены нетолько о методах построения быстрых программ, но и знать, когда их следует применить (желательно с минимальными программистскими усилиями).Измерение времени выполнения программНа время выполнения программы влияют следующие факторы.1.2.3.Ввод исходной информации в программу.Качество скомпилированного кода исполняемой программы.Машинные инструкции (естественные и ускоряющие), используемые для выполнения программы.4.

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

В качестве синонима дляэтого термина авторы часто используют выражение "время выполнения алгоритма". Отметим,что в первой части книги (до главы 6) авторами чаще используется последнее выражение, а вовторой — чаще термин "временная сложность". В этой связи заметим, что необходимо различать "время выполнения алгоритма" и "время выполнения программы". — Прим. ред.28ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВсписок элементов, подлежащих сортировке, а в качестве выходного результата — теже самые элементы, отсортированные в порядке возрастания или убывания. Например, входной список 2, 1, 3, 1, 5, 8 будет преобразован в выходной список 1, 1, 2< 3,5, 8 (в данном случае список отсортирован в порядке возрастания). -Естественноймерой объема входной информации для программы сортировки будет'число элементов, подлежащих сортировке, или, другими словами, длина входного списка, В об;щем случае длина входных данных т- Подходящая мера объема входной' информа?ции, и если не будет оговорено иное, то в качестве меры объема входной информациимы далее будем понимать именно длину входных данных.

;.. ^ •:Обычно говорят, что время выполнения программы имеет порядок, Г(п) от входныхданных размера п. Например, некая программа имеет время выполнения Г{га):=«гп2угде с — константа. Единица измерения Т(п) точно не определена, но мы будем пониматьТ(п) как количество инструкций, выполняемых на идеализированном кЪмйыотере. 'Для многих программ время выполнения действительно является функцией вход-:ных данных, а не их размера. В этой ситуации мы определяем Т(п) как время выполнения в наихудшем случае, i.e.

как максимум времени выполнения по всем входнымданным размера п. Мы также будем рассматривать Тер(п) к^к среднее (в статистнче^ском смысле) время выполнения по всем входным данным размера п. Хотя Tef(n) явл^-,ется достаточно объективной мерой времени выполнения, но часто, нельзя предполагать(или обосновать) равнозначность всех входных данных. На практике среднее время выполнения найти сложнее, чем ндихудщее время выполнения,'так как-г математическиэто трудноразрешимая задача и, кроме того, зачастую не имеет простого определенияпонятие "средних" входных данных. Поэтому в основном мы будем использовать наихудшее время выполнения как меру временной сложности алгоритмов, но не будем за-'бывать и о среднем времени выполнения там, где это возможно,Теперь сделаем замечание о втором и третьем факторах, влияющих на время выполнения программ: о компиляторе, используемом для компиляции программы, имашине, на которой выполняется программа.

Эти факторы влияют на то, что дляизмерения времени выполнения Т(п) мы не можем применить стандартные единицыизмерения, такие как секунды или миллисекунды. Поэтому мы можем только делитьзаключения, подобные "время выполнения такого-то алгоритма пропорционально2п ". Константы пропорциональности также нельзя точно определить, поскольку онизависят от компилятора, компьютера и других факторов.Асимптотические соотношенияДля описания скорости роста функций используется О-симвблйка. Например,' когда мы говорим, что время выполнения Т(п) некоторой программы имеет порядокО(п2) (читается "о-болыное от га в квадрате" или просто "о от п в квадрате"), то подразумевается, что существуют Положительные константы е й И 0 такие, чти для всехга, больших или равных га0, выполняется неравенство Т(п) < сп2.- ',Пример 1.4.

Предположим, что Т(0) = 1, Г(1) = 4 и в общем случае Т(п) =(га + I)2. Тогда Т(п) имеет порядок О(п): если положить га0 =•= 1 ; и : е =.4V то лески по-;казать, что для га 2: 1 будет выполняться неравенствр (п + I)2 Д 4га2, Отметим, чтонельзя положить га0 = 0, так как Т(0) = 1 и, следовательно, это значение при л.юбой,константе с больше сО 2 = 0. П,,-.,.,.•::;,.:;;,,.,:•Подчеркнем: мы предполагаем, что все функции времени выполнения рпредеденына множестве неотрицательных целых чисел и их значения также неотрицательны,,но необязательно целые.

Будем говорить, что Т(п) имеет порядок O(f(n)), если существуют константы с и п0 такие, что для всех л > га0 выполняется неравенствоТ(п) < cf(n). Для программ, у которых время выполнения имеет порядок O(/(n)), rQrворят, что они имеют порядок (или степень) роста {(п). . . .

. . .„ ,..-,,Пример 1.5. Функция Т(п) = Зл3 + 2га2 имеет степень роста О(га3). Чтобы это показать, надо положить га0 = 0 и с = 5, так как легко видеть, что для всех целых я ^ 0 выполняется неравенство Зга3 + 2га2 < 5л3. Можно, конечно, сказать, Что Т(л) имеет Поря4док О(га ), но это более слабое утверждение, чем то, что Г(л) имеет порядок'роста О(га )'.1.4. ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММ29В качестве следующего примера докажем, что функция 3" не может иметь порядок О(2"). Предположим, что существуют константы с и п0 такие, что для всех п > п0выполняется неравенство 3" < с2". Тогда с 2 (3/2)" для всех л > п0. Но (3/2)" принимает любое, как угодно большое, значение при достаточно большом п, поэтому несуществует такой константы с, которая могла бы мажорировать (3/2)" для всех п. ПКогда мы говорим, что Т(п) имеет степень роста О(/(га)), то подразумевается, что /(га)является верхней границей скорости роста Т(п).

Чтобы указать нижнюю границу скорости роста Т(п), используется обозначение: Т(п) есть £i(g(ra)) (читается "омега-большое отg(n)" или просто "омега от g(n)"), это подразумевает существование такой константы с,что бесконечно част? (для бесконечного числа значений п) выполняется неравенство1Т(п) > cg(n).323Пример 1.6. Для проверки того, что Т(п) = п + 2л есть й(л ), достаточно поло3жить с = 1. Тогда Т(п) > сп для га = О, 1,... .2Для другого примера положим, что Т(п) = п для нечетных га > 1 и Т(га) — п /ЮО —2для четных п > 0. Для доказательства того, что Т(п) есть Я(га ), достаточно положитьс = 1/100 и рассмотреть множество четных чисел га = 0, 2, 4, 6,...

. DОграниченность показателя степени ростаИтак, мы предполагаем, что программы можно оценить с помощью функций времени выполнения, Пренебрегая при этом константами пропорциональности. С этой2точки зрения программа с временем выполнения О(л ), например, лучше программыс временем выполнения О(га ). Константы пропорциональности зависят не только отиспользуемых компилятора и компьютера, но и от свойств самой программы. Пустьпри определенной комбинации компилятор-компьютер одна программа выполняется23за 100л миллисекунд, а вторая — за 5га миллисекунд.

Может ли вторая программабыть предпочтительнее, чем первая?Ответ на этот вопрос зависит от размера входных данных программ. При размеревходных данных га < 20 программа с временем выполнения 5га завершится быстрее,2чем программа с временем выполнения ЮОп . Поэтому, если программы в основномвыполняются с входными данными небольшого размера, предпочтение необходимоотдать программе с временем выполнения О(га3). Однако при возрастании га отношение времени выполнения 5л3/100л2 = л/20 также растет. Поэтому при больших лпрограмма с временем выполнения О(га2) становится предпочтительнее программы свременем выполнения О(га3). Если даже при сравнительно небольших л, когда времявыполнения обеих программ примерно одинаково, выбор лучшей программы представляет определенные затруднения, то естественно для большей надежности сделатьвыбор в пользу программы с меньшей степенью роста.Другая причина, заставляющая отдавать предпочтение программам с наименьшейстепенью роста времени выполнения, заключается в том, что чем меньше степеньроста, тем больше размер задачи, которую можно решить на компьютере.

Другимисловами, если увеличивается скорость вычислений компьютера, то растет также иразмер задач, решаемых на компьютере. Однако незначительное увеличение скоростивычислений компьютера приводит только к небольшому увеличению размера задач,решаемых в течение фиксированного промежутка времени, исключением из этогоправила являются программы с низкой степенью роста, как О(л) и О(га logra).Пример 1.7. На рис. 1.6 показаны функции времени выполнения (измеренные всекундах) для четырех программ с различной временной сложностью для одного и1Отметим асимметрию в определениях О- и О-символики. Такая асимметрия бывает полезной, когда алгоритм работает быстро на достаточно большом подмножестве, но не на всеммножестве входных данных.