Программирование на языке высокого уровня С/С++. Эффективность алгоритмов и сортировка
Математические методы анализа алгоритмов. Измерение эффективности алгоритмов, нахождение существенных различий. Быстродействие алгоритмов, степень роста временных затрат. Определение порядка алгоритма. Скорость роста некоторых функций, их свойства.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 27.03.2009 |
| Размер файла | 1,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2
Программирование на языке высокого уровня С/С++.
Эффективность алгоритмов и сортировка
Содержание
- Введение 3
- 1. Измерение эффективности алгоритмов 4
- 2. Три недостатка подхода, основанного на сравнении программ 5
- 3. Быстродействие алгоритмов 7
- 4. Степень роста временных затрат 9
- 5. Оценка порядка величины и обозначение О-большое 10
- 6. Основные понятия (определение порядка алгоритма) 11
- 7. Скорость роста некоторых функций 12
- 7. Эффективность алгоритмов поиска 19
- Заключение 23
- Литература 24
Введение
В этой лекции описаны математические методы анализа алгоритмов. Эти методы являются одной из главных тем, изучаемых компьютерными науками. Они позволяют сравнивать эффективность алгоритмов, пользуясь точными оценками. В качестве примеров рассматриваются алгоритмы поиска. Кроме того, в материале рассматривается сортировка данных, начиная с простых вопросов и заканчивая более сложными темами, связанными с рекурсией. Показано, что эффективность алгоритмов сортировки оценивается относительно легко.
1. Измерение эффективности алгоритмов
Сравнение алгоритмов между собой - основная тема компьютерных наук. Измерение эффективности алгоритмов чрезвычайно важно, поскольку выбор алгоритма сильно влияет на работу приложения. Эффективность алгоритмов, положенных в основу программы, определяет ее успех, будь то текстовый процессор, кассовый аппарат, банкомат, видеоигра или что-нибудь еще.
Допустим, два алгоритма решают одну и ту же задачу, например осуществляют поиск данных. Как их сравнить между собой и решить, какой из них лучше?
Выбирая алгоритм, оцените его эффективность.
До сих пор основное внимание мы уделяли человеческому фактору. В предыдущих главах акцент делался на стиле и читабельности программ. Было показано, что хорошо продуманные алгоритмы позволяют сократить время, необходимое для их программирования, а также облегчают сопровождение и модификацию программ. Основной задачей первой части книги было описание правильных приемов и стиля программирования. Хотя эта тема останется в поле нашего зрения и в дальнейшем, не стоит забывать о другом факторе - эффективности алгоритмов, которая определяет их выбор и способ реализации. Программы, представленные в книге, являются не только образцами хорошего стиля программирования, но и основаны на относительно эффективных алгоритмах.
Сравнение эффективности алгоритмов должно быть сосредоточено на их существенных различиях.
Анализ алгоритмов (analysis с algorithms) - это область компьютерных наук изучающая способы сравнения эффективности разных методов решения задач. Обратите внимание, что в этом определении использован термин "метод решения задачи", а не "программа". Следует подчеркнуть, что анализ алгоритмов, как правило, исследует существенные различия эффективности, которые обусловлены собственно методами решения задач, а не остроумными программистскими трюками. Изощренные приемы кодирования, позволяющие снизить стоимость вычислений, чаще всего снижают читабельность программы, тем самым повышая затраты на ее сопровождение и модификацию. Сравнение алгоритмов должно быть сосредоточено на их существенных различиях, поскольку именно их эффективность является основным фактором, определяющим общую стоимость решения, если два алгоритма выполняются несколько часов, а разница между временем их выполнения составляет несколько секунд, их эффективность одинакова.
При анализе эффективности одинаково важны как время выполнения алгоритма, так и занимаемая им память. Для анализа этих факторов используются Аналогичные методы. Поскольку в книге рассматриваются алгоритмы, не требующие значительных объемов памяти, в дальнейшем основное внимание будет уделяться их быстродействию.
Как сравнить быстродействие двух алгоритмов, решающих одну и ту же зав дачу? Для этого их можно запрограммировать на языке C++ и запустить обе программы. У этого подхода есть три существенных недостатка.
2. Три недостатка подхода, основанного на сравнении программ
1. Как запрограммированы алгоритмы?
Допустим, алгоритм А1 выполняется быстрее, чем алгоритм А2. Это может быть связано с тем, что программа, реализующая алгоритм ai, просто лучше написана. Следовательно, сравнивая время выполнения программ, вы на самом деле сравниваете реализации алгоритмов, а не сами алгоритмы. Реализации алгоритмов сравнивать бессмысленно, поскольку они очень сильно зависят от стиля программирования и не позволяют определить, какой из алгоритмов эффективнее.
2. На каком компьютере должны выполняться программы?
Особенности конкретного компьютера также не позволяют сравнить эффективность алгоритмов. Один компьютер может работать намного быстрее другого, поэтому для выполнения программ необходимо применять один и тот же компьютер. Какой компьютер выбрать? Конкретные операции, составляющие основу алгоритма А1 на одном из компьютеров могут выполняться быстрее, чем операции алгоритма А2, а на другом компьютере - наоборот. Сравнение эффективности алгоритмов не должно зависеть от особенностей конкретного компьютера.
3. Какие данные вводятся в программы?
Возможно, наиболее сложной проблемой является выбор тестовых данных. Всегда существует опасность, что при выборе конкретной тестовой задачи алгоритмы окажутся эффективнее, чем на самом деле. Например, сравнивая между собой последовательный и бинарный поиск элемента в упорядоченном массиве, можно предложить алгоритмам найти наименьший элемент. В этом случае алгоритм последовательного поиска сразу найдет искомый элемент. Следовательно, анализ эффективности не должен зависеть от выбора конкретных данных.
Анализ алгоритма не должен зависеть от конкретных реализаций, компьютеров и данных.
Чтобы преодолеть эти трудности, специалисты в области компьютерных наук разработали математические методы анализа алгоритмов, не зависящие от их конкретных реализаций, компьютеров и выбора тестовых данных. Как показано в следующем разделе, эти методы начинаются с подсчета основных операций, выполняемых при решении задачи.
3. Быстродействие алгоритмов
Основной способ оценки эффективности алгоритма - подсчет его операций.
В предыдущих главах мы неформально сравнивали между собой разные решения задач, подсчитывая количество выполняемых операций. Например, в главе 4 при сравнении реализаций абстрактного списка в виде массива и связанного списка оказалось, что функция retrieve позволяет непосредственно извлекать из массива n-й элемент списка, поскольку он хранится в ячейке items [n-1]. В то же время при извлеченного элемента из связанного списка нужно обойти весь список от начала до искомого элемента, на что потребуется n шагов.
Быстродействие алгоритма связано с количеством выполняемых операций, поэтому оценить его эффективность можно путем их простого подсчета. Рассмотрим еще несколько примеров.
Связанный список, допускающий обход. Напомним, что содержимое связанного списка, на который ссылается указатель head, можно вывести на экран с помощью следующего фрагмента программы.
Node *cur - head; < - 1 присваивание
while(cur! = NULL) < - n+l сравнений
{
cout " cur->item " endl; < - n операций записи
cur = cur->next; < - n присваиваний
} // Конец цикла while
Время, которое занимает вывод на экран содержимого связанного списка, прямо пропорционально количеству его узлов
В предположении, что связанный список состоит из n узлов, эти операторы выполняют n+l присваивание, n+l сравнение и n операций записи. Если каждое присваивание, сравнение и операция записи выполняется за a, b и c единиц времени, то на выполнение данного фрагмента программы уйдет (n+l) *(a+c) +n*w единиц времени. [Хотя в алгебре принято пропускать знак умножения, мы приводим его для наглядности.] Итак, можно интуитивно догадаться, что вывод на экран содержимого 100 узлов связанного списка будет выполняться дольше, чем вывод содержимого 10 узлов.
Ханойские башни. В главе 5 доказано, что решение задачи о ханойских башнях с n кольцами достигается за 2n-l шагов. Если каждый шаг выполняется за m единиц времени, то решение будет найдено за (2n-l) *m единиц времени. Как мы вскоре убедимся, при увеличении количества колец время решения задачи о ханойских башнях резко возрастает.
Вложенные циклы. Рассмотрим алгоритм, содержащий вложенные циклы.
for (i = 1 до n)
for (j = 1 до i)
for (k = 1 до 5)
Задача Т
Если задача T решается за t единиц времени, то на выполнение наиболее глубоко вложенного цикла по переменной k уйдет 5*t единиц времени. Цикл по переменной j затратит 5*t*i единиц времени, а внешний цикл по переменной i будет выполняться за
единиц времени.
4. Степень роста временных затрат
Время выполнения алгоритма выражается функцией, зависящей от размера задачи.
Описанные выше примеры демонстрируют, время выполнения алгоритма выражается функцией, зависящей от размера задачи. Способ измерения размера задачи зависит от конкретного приложения - количества узлов связанного списка, количества колец в задаче о ханойских башнях, размера массива или количества элементов стека. Итак, мы приходим к следующим выводам.
Для решения задачи, имеющей размер n, алгоритм А затрачивает п2/5 единиц времени.
Для решения задачи, имеющей размер n, алгоритм В затрачивает 5*n единиц времени.
Единицы времени, используемые при оценке эффективности этих алгоритмов, должны быть одинаковыми. Например, утверждение может выглядеть так.
Для решения задачи, имеющей размер n, алгоритм А затрачивает n2/5 секунд.
Выше мы уже перечислили трудности, возникающие на этом пути. На каком компьютере алгоритм будет выполнен за n2/5 секунд? Какая реализация этого алгоритма выполняется за n2/5 секунд? При каких данных алгоритм выполняется за n2/5 секунд?
Что конкретно нужно знать о быстродействии алгоритма? Важнее всего знать, насколько быстро возрастает время его выполнения с увеличением размера задачи. Степень роста временных затрат (growth rate) выражается следующими высказываниями.
Время выполнения алгоритма А прямо пропорционально n2.
Время выполнения алгоритма В прямо пропорционально п.
Сравнение эффективности алгоритмов при решении больших задач
По этим утверждениям нельзя определить, сколько именно времени выполняется алгоритм А или В. Главное, что при решении больших задач алгоритм В работает намного быстрее. Иными словами, объем времени, затрачиваемый алгоритмом В, выраженный функцией, зависящей от размера задачи, растет медленнее, чем время выполнения алгоритма А, поскольку линейная функция растет медленнее квадратичной. Даже если В действительно затрачивает 5*n секунд, в то время как алгоритм А выполняется за n2/5 секунд, в целом алгоритм В выполняется значительно быстрее алгоритма А. Эта ситуация проиллюстрирована на рис.1. Таким образом, выражение Время выполнения алгоритма А прямо пропорционально n2 точно характеризует эффективность алгоритма и не зависит от конкретных компьютеров и реализаций.
Рисунок 1. Время выполнения алгоритмов как функция, зависящая от размера задачи n.
5. Оценка порядка величины и обозначение О-большое
Допустим, выполняется следующее утверждение.
Время выполнения алгоритма А прямо пропорционально функции f(n).
В таких случаях говорят, что алгоритм А имеет порядок f(n) (order f(n)). Этот факт обозначается как O(f(n)). Функция f(n) называется сложностью алгоритма (growth-rate function). Поскольку в обозначении используется прописная буква O (первая буква слова order (порядок)), оно называется обозначением О-большое (Big-O notation). Если время решения задачи прямо пропорционально ее размеру n, то сложность задачи равна O(n), т.е. имеет порядок n. Если время решения задачи прямо пропорционально квадрату ее размера, т.е. n2, то сложность задачи равна O(n2) и т.д.
6. Основные понятия (определение порядка алгоритма)
Алгоритм А имеет порядок f(n). Этот факт обозначается как O(f(n)), если существуют константы k и n0 такие, что при решении задачи, имеющей размер n?n0 алгоритм А выполняется не более чем за k* f(n) единиц времени.
Условие n?n0 формализует интуитивное понятие большой задачи. Как правило, этому определению удовлетворяет большинство значений переменных k и n. Проиллюстрируем определение несколькими примерами.
* Допустим, что при решении задачи, имеющей размер n, алгоритм выполняется за n2-3*n+10 секунд. Если существуют такие константы k и n0, что
k * n2 > n2 - 3*n + 10 для всех n ? n0,то алгоритм имеет порядок n2. Фактически если константа k равна 3, а число n0 равно 2, то
3 * n2 > n2 - 3*n + 10 для всех n > 2,как показано на рис.2. Таким образом, при n > n0 для выполнения алгоритма потребуется не более k * n2 единиц времени.
Рисунок 2. Если n > 2, то 3 * n2 больше, чем n2 - 3 * n + 10
* Ранее мы показали, что для вывода на экран первых n элементов связанного списка потребуется (n+l) *(a+c) +n*w единиц времени. Поскольку неравенство 2*n ? n+l выполняется для всех n ? 1, имеет место неравенство
(2*a+2*c+w) *n ? (n+l) *(a+c) +n*w для всех n > 1.
Следовательно, сложность задачи имеет порядок O(n). Здесь константа k равна числу 2*a+2*c+w, а константа n0 равна 1.
Для решения задачи о ханойских башнях потребуется (2n-l) *m единиц времени. Поскольку для всех n ? 1 выполняется неравенство
m*2n > (2n-l) *m,
эта задача имеет сложность O(2n).
Требование n > n0 в определении величины O(f(n)) означает, что оценка времени будет корректной лишь для достаточно больших задач. Иными словами, если задача имеет относительно небольшие размеры, то оценка времени ее решения будет слишком заниженной. Например, функция log n равна 0, если число n равно 1. Итак, из того, что число k * log 1 равно 0 при любых значениях константы k, следует неправильная оценка времени. Для выполнения любого алгоритма требуется ненулевое количество единиц времени, даже если размер задачи равен 1. Следовательно, если f(n) = log n, задачу при n = 1 следует рассматривать отдельно.
7. Скорость роста некоторых функций
Чтобы подчеркнуть значение правильной оценки степени роста функции, рассмотрим таблицу и график, представленные на рис.3. В таблице (рис.3, а) показаны разные значения аргумента n и приближенные значения некоторых функций, зависящих от n, в порядке увеличения скорости их роста.
O(1) < O(log2n) < O(n) < O(n*log2n) < O(n2) < O(n3) < O(2n)
По этой таблице можно оценить относительную скорость роста значений различных функций. (На рис.3, б показаны графики этих функций. [Функция f(n) =l на рисунке не показана, поскольку она не соответствует выбранному к штабу. Ее график представляет собой линию, проходящую через точку y=l параллельно оси x.])
Таблица
Интуитивная интерпретация сложности алгоритма
|
1 log2n n n*log2n n2 n3 2n |
Константа 1 означает, что время выполнения алгоритма постоянно и, следовательно, не зависит от размера задачи Время выполнения логарифмического алгоритма (logarithmic algorithm) медленно возрастает с увеличением размера задачи. Если размер задачи возводится в квадрат, ее сложность увеличивается всего в два раза. Позднее мы убедимся, что алгоритм бинарного поиска обладает именно такими свойствами. Напомним, что при бинарном поиске массив делится пополам, а затем поиск продолжается в одной из полученных половин массива. Обычно логарифмические алгоритмы решают задачу, сводя ее к задаче меньшего размера. Основание логарифма не влияет на сложность алгоритма, поэтому его можно не указывать Время выполнения линейного алгоритма (linear algorithm) прямо пропорционально размеру задачи. Если размер задачи возводится в квадрат, объем времени увеличивается точно так же Время выполнения алгоритма, имеющего сложность O(n*log2n) растет быстрее, чем у линейного алгоритма. Такие алгоритмы обычно разбивают задачи на подзадачи и решают их по отдельности. Пример такого алгоритма - сортировка слиянием - рассматривается далее Время выполнения квадратичного алгоритма (quadratic algorithm) быстро возрастает с увеличением размера задачи. В алгоритмах такого типа часто используются два вложенных цикла. Такие алгоритмы следует применять лишь для решения небольших задач. Далее в этой главе мы изучим несколько квадратичных алгоритмов сортировки Время выполнения кубического алгоритма (qubic algorithm) еще быстрее возрастает с увеличением размера задачи по сравнению с квадратичным. Алгоритмы, использующие три вложенных цикла, часто оказываются кубическими. Такие алгоритмы следует применять лишь для решения небольших задач С увеличением размера задачи время выполнения экспоненциального алгоритма (exponential algorithm) обычно резко возрастает, поэтому на практике такие алгоритмы применяются редко |
Если сложность алгоритма A пропорциональна функции f(n), а сложность алгоритма B пропорциональна функции g, которая растет медленнее, чем функция f, то совершенно очевидно, что алгоритм B эффективнее алгоритма А, если размер решаемой задачи достаточно велик. Сложность алгоритма является решающим фактором при оценке его эффективности.
Для упрощения анализа алгоритмов будем использовать некоторые математические свойства обозначения О-большое. При этом следует иметь в виду, что запись O(f(n)) означает "порядка f(n)" или "имеет порядок f(n)". Символ О - это не функция.
Некоторые свойства функций:
1. При оценке сложности алгоритма можно учитывать только старшую степень.
Например, если алгоритм имеет сложность O(n3 + 4*n2 + 3*n), он имеет порядок O(n3). Из таблицы, показанной на рис.9.3, а, видно, что слагаемое n3 намного больше, чем слагаемые 4*n2 и 3*n, особенно при больших значениях n, когда порядок функции n3 + 4*n2 + 3*n совпадает с порядком функции n3. Иначе говоря, эти функции имеют одинаковый порядок роста. Итак, даже если сложность алгоритма равна O(n3 + 4*n2 + 3*n), можно говорить, что он имеет порядок просто O(n3). Как правило, алгоритмы имеют сложность O(f(n)), где функцией f(n) является одна из функций, перечисленных на рис.3.
а)
б)
Рисунок 3. Сравнение сложности алгоритмов: а) в табличном виде; б) в графическом виде
2. При оценке сложности алгоритма можно игнорировать множитель при старшей степени.
Например, если алгоритм имеет сложность O(5*n3), можно говорить, что он имеет порядок O(n3). Это утверждение следует из определения величины O(f(n)), если положить k = 5.
3.0(f(n)) +O(g(n)) =O(f(n) +g(n)).
Функции, описывающие сложность алгоритма, можно складывать. Например, если алгоритм имеет сложность О(n2) +О(n), то говорят, что он имеет сложность О(n2+n). В соответствии с п.1, это можно записать просто как O(n2). Аналогичные правила выполняются для умножения.
Из указанных выше свойств следует, что при оценке эффективности алгоритма нужно оценить лишь порядок его сложности. Точная формула, описывающая сложность алгоритма, зачастую весьма сложна, а иногда и просто невозможна.
При решении задач одинаковой размерности время выполнения алгоритма может изменяться.
Наихудший и средний варианты. При решении конкретных задач одинаковой размерности время выполнения алгоритма может оказаться разным. Например, время, необходимое для поиска n элементов, может зависеть от природы самих элементов. Обычно оценивается максимальное время, необходимое для решения задачи размера n, т.е. наихудший вариант. Анализ наихудшего варианта (worts-case analysis) приводит к оценке 0(f(n)), если при решении задачи, имеющей размер n, в наихудшем случае алгоритм выполняется не более чем за k*f(n) единиц времени для всех значений n, за исключением их конечного числа. Хотя анализ наихудшего варианта приводит к пессимистическим оценкам, это не означает, что алгоритм всегда будет работать медленно. Следует иметь в виду, что наихудший вариант на практике встречается редко.
Анализ среднего варианта (average-case analysis) позволяет оценить среднее время выполнения алгоритма при решении задачи размера n. Говорят, что среднее время выполнения алгоритма A равно O(f(n)), если при решении задачи размера n оно не превышает величины k*f(n) для всех значений n, за исключением их конечного числа. Как правило, анализ среднего варианта выполнить намного сложнее, чем анализ наихудшего варианта. Одна из трудностей заключается в определении вероятностей появления разных задач одинаковой размерности. Вторая трудность заключается в вычислении распределений разных значений. Анализ наихудшего варианта легче поддается вычислениям и поэтому выполняется намного чаще.
Перспективы:
Сложность операции retrieve при реализации абстрактного списка в виде массива равна O(1).
Прежде чем перейти к оценкам порядка величин, характеризующих сложность конкретных алгоритмов, имеет смысл остановиться на перспективах. В качестве примера рассмотрим абстрактный список, состоящий из n элементов. Ранее мы уже видели, что при реализации абстрактного списка в виде массива операция retrieve имеет прямой доступ к i-му элементу списка независимо от значения n. На извлечение 1-го и 100-го элементов списка операция retrieve затрачивает одинаковое количество времени. Следовательно, сложность операции retrieve при реализации абстрактного списка в виде массива равна O(1).
Сложность операции retrieve при реализации абстрактного списка в виде связанного списка равна O(n).
Однако при реализации абстрактного списка в виде связанного списка операция retrieve выполняет n шагов, прежде чем найдет n-й элемент. Следовательно, ее сложность равна O(n).
Анализируя алгоритмы, следует иметь в виду, что нас интересуют только существенные различия в оценках эффективности. Можно ли считать существенными описанные выше различия при оценке эффективности операции retrieve? При возрастании размера связанного списка для извлечения искомого элемента потребуется все больше времени, хотя время доступа к элементам массива постоянно. Итак, по мере увеличения длины списка различие между временем выполнения операции retrieve в разных реализациях рано или поздно станет существенным. В нашем примере оценки эффективности операции retrieve начинают различаться, если список достаточно велик. Если количество элементов списка не превышает 25, разницы между оценками эффективности операции retrieve в разных реализация абстрактного списка вообще нет.
Выбирая реализацию абстрактного типа данных, пытайтесь оценить, насколько часто в конкретном приложении выполняется та или иная операция.
Рассмотрим конкретное приложение - например, проверку орфографии в текстовом процессоре, - которое часто извлекает элемент из списка, однако редко вставляет их туда или удаляет. Поскольку операция retrieve c массивами работает быстрее, чем со связанны списками, в этом случае следует предпочесть реализацию абстрактного списка в виде массива. С другой стороны, если в приложении часто выполняются операции вставки и удаления элементов, следует выбрать связанный список. °°Р реализации абстрактного типа данных сильно зависит от того, насколько 0 в данном приложении выполняется та или иная операция. В следующей главе мы будем часто сталкиваться с такими ситуациями.
Редкие, но важные операции должны быть эффективными.
Время выполнения некоторых операций над абстрактным типом данных может оказаться крайне важным, несмотря на то что эти операции могут выполняться относительно редко. Например, в системе управления полетами может быть предусмотрена аварийная операция, предотвращающая столкновение двух самолетов. Очевидно, эта операция должна выполняться как можно быстрее, даже если она применяется очень редко. Итак, выбирая реализацию абстрактного типа данных, необходимо проанализировать выполняемые операции, а также оценить частоту и время их выполнения.
Вскоре мы сравним два алгоритма поиска, один из которых имеет эффективность O(n), а другой - O(log2n). Несмотря на то, что алгоритм, имеющий сложность O(log2n), c большими массивами работает быстрее, на небольших массивах (n < 25) их эффективность различить невозможно. В принципе вполне возможно, что алгоритм, имеющий сложность O(n), с маленькими массивами работает быстрее, поскольку в определение его эффективности входит константа k. Однако значительное различие в быстродействии этих алгоритмов проявляется лишь при решении больших задач. Это явление продемонстрировано на рис. 1.
Если размер задачи невелик, эффективностью алгоритма можно пренебречь.
Итак, если максимальный размер задачи невелик, время выполнения алгоритмов разной сложности не будет значительно отличаться. Если заранее известно, что размер задачи никогда не будет больше, анализ эффективности алгоритмов можно не проводить. В таких случаях следует выбрать наиболее простой алгоритм, запрограммировать его и протестировать.
Следует стремиться к равновесию между быстродействием алгоритма и объемом занимаемой им памяти.
Довольно часто при оценке эффективности алгоритмов нужно отыскать компромисс между быстродействием и занимаемым объемом памяти. Редко удается определенно сказать: "Этот метод является наилучшим способом решения данной задачи. " Решение, которое выполняется относительно быстро, часто выдвигает завышенные требования к памяти компьютера. Иногда невозможно определенно сказать, что один алгоритм работает быстрее другого. Одни операции алгоритм A может выполнять быстрее, чем алгоритм B, а другие - наоборот. В силу этих причин, анализируя эффективность алгоритмов, нужно ориентироваться на конкретное приложение.
Сравнение стиля и эффективности алгоритмов.
Итак, стиль и эффективность алгоритма одинаково важны. При анализе следует концентрироваться только на значительных различиях эффективности и не прибегать к программистским трюкам ради экономии нескольких миллисекунд. Более тщательный анализ эффективности связан с вопросами программирования, которые не следует рассматривать на этапе разработки алгоритма. Если вам удалось разработать метод решения задачи, эффективность которого значительно превышает эффективность остальных алгоритмов, смело выбирайте его, если размер задачи относительно велик. Если размер задачи невелик, возможно, лучшим окажется не самый эффективный алгоритм Иными словами, если задача невелика, на первый план выступают другие факторы, например простота алгоритма.
Анализ сложности алгоритмов ориентируется на большие задачи.
Фактически при анализе сложности алгоритма неявно предполагается, что он будет применяться для решения больших задач. Это предположение позволяет сосредоточиться только на порядке сложности алгоритма, пренебрегая другими факторами, поскольку при решении больших задач менее сложный алгоритм выполняется быстрее.
7. Эффективность алгоритмов поиска
В качестве еще одного примера рассмотрим два алгоритма поиска: последовательный и бинарный поиск элемента в массиве.
Последовательный поиск. Наихудший вариант O(n), средний вариант O(n), наилучший вариант O(1).
Последовательный поиск. При последовательном поиске элемента в массиве, имеющем длину n, элементы просматриваются по очереди, начиная с первого, пока не обнаружится искомый, либо не будет достигнут конец массива. В наилучшем случае искомым элементом является первый. Для его обнаружения понадобится только одно сравнение. Следовательно, в наилучшем случае сложность алгоритма последовательного поиска равна O(1). В наихудшем случае искомый элемент является последним. Для того чтобы его найти, понадобится n сравнений. Следовательно, в наихудшем случае сложность алгоритма последовательного поиска равна O(n). В среднем случае искомый элемент находится в средней ячейке массива и обнаруживается после n/2 сравнений.
Каков порядок алгоритма, если элемент не найден? Зависит ли его порядок от того, упорядочены элементы массива или нет? Эти вопросы для самопроверки читатели должны рассмотреть самостоятельно.
Бинарный поиск. Является ли бинарный поиск более эффективным, чем последовательный? Алгоритм бинарного поиска, описанный в главе 2, предназначен для поиска элемента в упорядоченном массиве и основан на повторяющемся делении частей массива пополам. Алгоритм определяет, в какой из двух частей находится элемент, если он действительно хранится в массиве, а затем повторяет процедуру деления пополам. Итак, в ходе бинарного поиска возникает несколько массивов меньшего размера, причем каждый раз размер очередного массива уменьшается вдвое по сравнению с предыдущим.
В ходе очередного разбиения массива алгоритм выполняет сравнения. Сколько сравнений выполняет алгоритм при поиске элемента в массиве, имеющем длину n? Точный ответ на этот вопрос, разумеется, зависит от позиции искомого элемента в массиве. Однако можно вычислить максимальное количество сравнений, т.е. наихудший вариант. Допустим, что n = 2*k, где k - некоторое натуральное число. Алгоритм поиска выполняет следующие шаги.
1. Проверяет среднюю ячейку массива, имеющего длину n.
2. Проверяет среднюю ячейку массива, имеющего длину n/2.
3. Проверяет среднюю ячейку массива, имеющего длину n/22 и т.д.
Чтобы проверить среднюю ячейку массива, сначала нужно поделить массив пополам. После того как массив, состоящий из n элементов, поделен пополам, делится пополам одна из его половин. Эти деления продолжаются до тех пор, пока останется только один элемент. Для этого потребуется выполнить k разбиений массива. Это возможно, поскольку n/2k=l. (Напомним, что n = 2k) B наихудшем случае алгоритм выполнит k разбиений и, следовательно, k сравнений. Поскольку n = 2k, получаем, что k = log2n.
Чтo произойдет, если число n не будет степенью двойки? Легко найти наименьшее число k, удовлетворяющее условию 2k-1 < n < 2k.
(Например, если n равно 30, то k=5, поскольку 24 = 16 < 30 < 32 < 25) Алгоритм по-прежнему выполнит по меньшей мере k разбиений, пока не возникнет массив, состоящий из одного элемента. Итак, получаем следующие оценки.
k-l < log2n < k,
k < l+log2n< k+1,k ? l+log2n.
В наихудшем случае сложность бинарного поиска равна O(log2n).
Следовательно, в наихудшем случае сложность бинарного поиска оценивается величиной O(log2n), если n?2k. В принципе сложность алгоритма в наихудшем случае имеет порядок O(log2n) для любого значения n.
Можно ли утверждать, что бинарный поиск лучше последовательного? Намного лучше! Например, log21000000 = 19, поэтому алгоритм последовательного поиска выполнит миллион сравнений, в то время как алгоритм бинарного поиска - не более 20. Если массивы велики, бинарный поиск намного эффективнее последовательного.
Однако следует иметь в виду, что условие упорядоченности массива приводит к дополнительным затратам, которые могут стать существенными.
Заключение
Сортировка (sorting) - это процесс упорядочения набора элементов в возрастающем или убывающем порядке. Сортировка необходима во многих ситуациях. Например, иногда нужно упорядочить данные, прежде чем включить их в отчет. Однако чаще всего сортировка выполняется в качестве первого шага некоторых алгоритмов. Например, поиск данных является одной из наиболее распространенных задач, выполняемых компьютерами. Если набор данных достаточно велик, необходимо применять эффективный метод, например алгоритм, бинарного поиска. Однако для применения алгоритма бинарного поиска необходимо, чтобы массив был упорядочен. Следовательно, если исходный набор не был упорядочен, сортировка данных должна предшествовать бинарному поиску.
Литература
1. Ричард Хэзфилд, Лоуренс Кирби и др. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста. - Киев: Издательство "ДиаСофт", 2001.
2. Каррано Ф.М., Причард Дж.Дж. Абстракция данных и решение задач на С++. - М.: Издательский дом "Вильямс", 2003.
Подобные документы
Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.
курсовая работа [1,7 M], добавлен 16.04.2012Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.
дипломная работа [1,6 M], добавлен 12.08.2017Разработка алгоритмов методом пошаговой детализации. Типы данных и операции в Turbo-Pascal. Организация работы с подпрограммами. Составление алгоритмов и программ задач с использованием конечных сумм. Организация работы с динамическими переменными.
учебное пособие [1,4 M], добавлен 26.03.2014Анализ алгоритмов, оценка параметров алгоритма (эффективности, сложности, правильности). Комплексный анализ эффективности алгоритма на основе комплексной оценки ресурсов формальной системы. Верификация при коллективной разработке программных систем.
презентация [234,9 K], добавлен 22.10.2013Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения определенного интеграла. Анализ работы подпрограмм. Разработка тестов для проверки правильности алгоритмов.
контрольная работа [831,0 K], добавлен 24.11.2013Основные особенности эволюционных алгоритмов. Описание алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов. Вычисление функции приспособленности. Программная реализация. Тестирование и руководство пользователя.
курсовая работа [1,3 M], добавлен 11.03.2014Положения алгоритмов сжатия изображений. Классы приложений и изображений, критерии сравнения алгоритмов. Проблемы алгоритмов архивации с потерями. Конвейер операций, используемый в алгоритме JPEG. Характеристика фрактального и рекурсивного алгоритмов.
реферат [242,9 K], добавлен 24.04.2015Исследование особенностей разработки линейных алгоритмов и их реализации в среде Delphi. Составление тестов для проверки программы. Характеристика основных элементов интерфейса, компонентов, значения их свойств. Построение графической схемы алгоритма.
лабораторная работа [316,6 K], добавлен 08.11.2012Комплексное исследование истории развития, основных понятий, области применения и особенностей генетических алгоритмов. Анализ преимуществ генетических алгоритмов. Построение генетического алгоритма, позволяющего находить максимум целочисленной функции.
курсовая работа [27,9 K], добавлен 23.07.2011Обзор рекурсивных алгоритмов с позиции теории алгоритмов, теории сложности, с точки зрения практического программирования. Имитация работы цикла с помощью рекурсии. Способы изображения древовидных структур. Синтаксический анализ арифметических выражений.
курсовая работа [432,2 K], добавлен 16.01.2013
