Лекция Анализ алгоритмов. Анализ алгоритмов
 Скачать 0.53 Mb.
|
|
1 Анализ алгоритмов Оглавление Анализ алгоритмов .................................................................................................. 2 Бинарный поиск ....................................................................................................... 5 Примечание! ........................................................................................................ 8 Время выполнения ................................................................................................ 10 «О-большое» .......................................................................................................... 10 Типичные примеры «О-большого» ................................................................. 13 Расчет сложности. Отбрасывание констант и несущественной части ........ 14 Примеры «О-большое» ..................................................................................... 15 Сложность встроенных методов ...................................................................... 15 Складывать или умножать? .............................................................................. 17 Анализ поиска максимального элемента в массиве .......................................... 18 Анализ алгоритма сортировки выбором ............................................................. 19 Оценка алгоритмов, количество итераций которых не задано явно ............... 21 Анализ рекурсивных алгоритмов ........................................................................ 24 2 Анализ алгоритмов Одну и ту же задачу можно решить с помощью различных алгоритмов. Анализ алгоритмов дает нам инструмент для выбора оптимального. Характеристики, описывающие эффективность работы алгоритма: •время выполнения – приблизительное число операций, выполняемых алгоритмом; •скорость роста числа операций – зависимость числа операций алгоритма от размера входных данных; •объем памяти – память, необходимая для выполнения алгоритма. Будем рассматривать изучение анализа алгоритмов, на примере двух самых известных: простой поиск и бинарный поиск. При анализе эффективности алгоритмов первична оценка времени работы алгоритма, поскольку в большинстве известных алгоритмов требования к памяти обычно не превосходят величины, кратной объему обрабатываемой информации. В тех случаях, когда память играет существенную роль, необходимо оценить эффективность алгоритма и с этой точки зрения. Анализ алгоритмов соответствует следующим принципам: 1. Игнорировать зависимость от конкретной ЭВМ – характеристики ЭВМ, на которой выполняется реализующая алгоритм программа, не должны учитываться при анализе его эффективности, поскольку при переносе программы на более быстрый компьютер, алгоритм не становится лучше (несмотря на то, что работает быстрее); 2. Анализировать изменение О(n) при n→∞, где О(n) – время работы алгоритма с задачей размерности n. Даже не эффективный алгоритм при работе с небольшим количеством входных данных часто завершает работу за допустимое время. Следовательно, чтобы выявить недостатки, работу алгоритма нужно оценивать при достаточно больших n. 3. Темп(порядок) роста. В асимптотическом анализе исследуется общее поведение функции при увеличении входного параметра, поэтому в 3 выражении О(n) во внимание принимается только главный член без постоянного множителя (при больших n членами меньшего порядка можно пренебречь). Разница между алгоритмом, который делает n + 5 операций и тем, который делает n + 250 операций, становится не заметной при n→∞. Классы входных данных При анализе алгоритма очень важно оценить его эффективность на всех возможных наборах данных: 1. Наилучший случай – такой набор данных, на котором алгоритм выполняется за минимальное время, то есть выполняется меньше всего действий. 2. Наихудший случай – набор данных, на котором алгоритм выполняется за максимальное время. 3. Средний случай. В основе анализа данного случая лежит определение различных групп, на которые следует разбить возможные входные наборы. Далее определяется вероятность, с которой входной набор данных принадлежит каждой группе. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы. Среднее время работы алгоритма: 𝐴(𝑛) = ∑ 𝑝 𝑖 (𝑛)𝑡 𝑖 (𝑛) 𝑚 𝑖=1 Где 𝑛– размер входных данных, 𝑚– число групп, 𝑝 𝑖 (𝑛)- вероятность того, что входные данные принадлежат группе с номером i, а через 𝑡 𝑖 (𝑛)- время, необходимое алгоритму для обработки данных i-ой группы. Предположим, что мы исследуем алгоритм поиска, тогда: • набор данных является наилучшим, если искомое значение записано в первой проверяемой алгоритмом ячейке; • наихудшим, если искомое значение находится в проверяемом списке последним или вообще отсутствует. • предположим, что в качестве входных множеств у нас имеются все перестановки 10-ти различных чисел (количество таких перестановок равно 10!=3 628 800 ). Тогда класс, к которому относится такой список из 10-ти 4 чисел, определяется тем, на каком месте в нем находится наибольший элемент (т.е. m = 10). Если наибольший элемент находится на первом месте (к этому классу относится 362880 входных множеств), то время работы алгоритма поиска будет наименьшим. 5 Бинарный поиск Предположим, вы ищете фамилию человека в телефонной книге (какая древняя технология!). Она начинается с буквы «К». Конечно, можно начать с самого начала и перелистывать страницы, пока вы не доберетесь до буквы «К». Но скорее всего для ускорения поиска лучше раскрыть книгу на середине: ведь буква «К» должна находиться где-то ближе к середине телефонной книги. Или предположим, что вы ищете слово в словаре, и оно начинается с буквы «О». И снова лучше начать с середины. Теперь допустим, что вы вводите свои данные при входе в VK. При этом VK необходимо проверить, есть ли у вас учетная запись на сайте. Для этого ваше имя пользователя нужно найти в базе данных. Допустим, вы выбрали себе имя пользователя “kotmarkot”. VK может начать с буквы А и проверять все подряд, но разумнее будет начать с середины. Перед нами типичная задача поиска. И во всех этих случаях для решения задачи можно применить один алгоритм: бинарный поиск. Бинарный поиск — это алгоритм; на входе он получает отсортированный список элементов (позднее я объясню, почему он должен быть отсортирован). Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null. Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: было загадано число от 1 до 100. 11 22 33 ю… 1100 Вы должны отгадать число, использовав как можно меньше попыток. При каждой попытке можно давать один из трех ответов: «мало», «много» или «угадал». 6 Предположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, … Вот как это будет выглядеть: Плохой способ — это угадать число. Это пример простого поиска. При каждой догадке исключается только одно число. Если загадали число 99, то, чтобы добраться до него, потребуется 99 попыток! Существует другой, более эффективный способ. Начнем с 50. МАЛО 1 2 МАЛО 7 МАЛО 7 Слишком мало ... но только что исключили половину чисел! Теперь мы знаем, что все числа 1-50 меньше загаданного. Следующая попытка: 75. На этот раз оно больше искомого. Но снова исключили половину оставшихся чисел! С бинарным поиском каждый раз загадываем число в середине диапазона и исключаем половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75). 50 МАЛО 75 МНОГО 63 МНОГО 8 Так работает бинарный поиск. Какое бы число я ни задумали, гарантированно сможем угадать его не более чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел! Предположим, ищем слово в словаре с 240000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае? ПРОСТОЙ ПОИСК: ____________ШАГОВ БИНАРНЫЙ ПОИСК: __________ШАГОВ В общем случае для списка из п элементов бинарный поиск выполняется за 𝑙𝑜𝑔 2 𝑛 шагов, тогда как простой поиск будет выполнен за 𝑛 шагов. Примечание! Логарифмы 𝑙𝑜𝑔 10 100 по сути означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ – 2: 10*10. Логарифм – операция обратная возведению в степень. Логарифмом числа 𝑥 по основанию 𝑏 (𝑏 > 𝑂 𝑢 𝑏 ≠ 1) называется такой показатель степени 𝑎, в которую нужно возвести 𝑏, чтобы получить 𝑥 ( 𝑙𝑜𝑔 𝑏 𝑥 = 𝑎, тогда и только тогда, когда 𝑏 𝑎 = 𝑥). 100 50 25 13 7 4 2 1 57 ДА! 9 Данная функция является взаимно однозначной (если log 𝑏 𝑥 = log 𝑏 𝑦, то𝑥 = 𝑦) и обладает следующими свойствами: 𝑙𝑜𝑔 𝑏 1 = 0, 𝑙𝑜𝑔 𝑏 𝑏 = 1, 𝑙𝑜𝑔 𝑏 (𝑥𝑦) = 𝑙𝑜𝑔 𝑏 (𝑥) + 𝑙𝑜𝑔 𝑏 (𝑦), log 𝑏 𝑥 𝑦 = 𝑦 log 𝑏 𝑥, 𝑙𝑜𝑔 𝑎 𝑥 = 𝑙𝑜𝑔 𝑏 𝑥 𝑙𝑜𝑔 𝑏 𝑎 – Замена основания логарифма. Функция является строго возрастающей при 𝑏 > 1 и строго убывающей при 0 < 𝑏 < 1. Посмотрим, как написать реализацию бинарного поиска на С++. В следующем примере кода используется массив. Нумерация ячеек начинается с 0: первая ячейка находится в позиции с номером 0, вторая в позиции с номером 1 и т. д. Функция binary_search получает отсортированный массив и значение. Если значение присутствует в массиве, то функция возвращает его позицию. При этом мы должны следить за тем, в какой части массива проводится поиск. Код: int * bynary_serch( int * a , int n , int item ) { int low = 0; int high = n - 1; while (low <= high) { int mid = (low + high) / 2; int guess = a [mid]; if (guess == item ) return a +mid; else if (guess < item ) low = mid + 1; else high = mid - 1; } return nullptr ; } 10 Время выполнения Каждый раз, когда рассматривают очередной алгоритм, говорят о времени его выполнения. Обычно следует выбирать самый эффективный алгоритм, будь то оптимизация по времени или памяти. Вернемся к бинарному поиску. Сколько времени с экономит его применение? В первом варианте мы последовательно проверяли каждое число, одно за другим. Если список состоит из 100 чисел, может потребоваться до 100 попыток. Для списка из 4 миллиардов чисел потребуется до 4 миллиардов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным. С бинарным поиском дело обстоит иначе. Если список состоит из 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элементов потребуется не более 32 попыток. Бинарный поиск выполняется за логарифмическое время. «О-большое» Специальная нотация «О-большое» описывает скорость работы алгоритма. Время от времени вам придется использовать чужие алгоритмы, а потому неплохо было бы понимать, насколько быстро или медленно они работают. Боб пишет алгоритм поиска для NASA. Его алгоритм заработает, когда ракета будет подлетать к Луне, и поможет вычислить точку посадки. Это один из примеров того, как время выполнения двух алгоритмов растет с разной скоростью. Боб пытается выбрать между простым и бинарным поиском. Его алгоритм должен работать быстро и правильно. С одной стороны, бинарный поиск работает быстрее. У Боба есть всего 10 секунд, чтобы выбрать место посадки; если он не уложится в это время, то момент для посадки будет упущен. С другой стороны, простой поиск пишется 11 проще и вероятность ошибок в нем ниже ... Конечно, Боб совершенно не хочет допустить ошибку в коде посадки ракеты. И тогда для пущей уверенности Боб решает измерить время выполнения обоих алгоритмов для списка из 100 элементов. Допустим, проверка одного элемента занимает 1 миллисекунду (мс). При простом поиске Бобу придется проверить 100 элементов, поэтому поиск займет 100 мс. С другой стороны, при бинарном поиске достаточно проверить всего 7 элементов (𝑙𝑜𝑔 2 100 равен приблизительно 7), а поиск займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения простого поиска? А при бинарном поиске? Боб проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс (𝑙𝑜𝑔 2 1000000000 равен приблизительно 30). «32 мс! -думает Боб. - Бинарный поиск в 15 раз быстрее простого, потому что простой поиск для 100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой поиск займет 30 х 15 = 450 мс, верно? Гораздо меньше отведенных 10 секунд». И Боб выбирает простой поиск. Верен ли его выбор? Нет, Боб ошибается. Глубоко ошибается. Время выполнения для простого поиска с 1 миллиардом элементов составит 1 миллиард миллисекунд, а это 11 дней! Проблема в том, что время выполнения для бинарного и простого поиска растет с разной скоростью. Другими словами, с увеличением количества элементов бинарный поиск занимает чуть больше времени. А простой поиск займет гораздо больше времени. Таким образом, с увеличением списка бинарный список внезапно начинает работать гораздо быстрее простого. Боб думал, что бинарный поиск работает в 15 раз быстрее простого, но это не так. Если список состоит из 1 миллиарда элементов, бинарный поиск работает приблизительно в 33 миллиона раз быстрее. Бот почему недостаточно знать, сколько времени должен работать алгоритм, - необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь-то и пригодится «О-большое». 12 «О-большое» описывает, насколько быстро работает алгоритм. Предположим, имеется список размера 𝑛. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить 𝑛 операций. Время выполнения «О-большое» имеет вид О(n). Постойте, но где же секунды? А их здесь нет – «О-большое» не сообщает скорость в секундах, а позволяет сравнить количество операций. Оно указывает, насколько быстро возрастает время выполнения алгоритма. Для бинарного поиска «О-большое» имеет вид О(log n).Такая запись сообщает количество операций, которые придется выполнить алгоритму. Она называется «О-большое», потому что перед количеством операций ставится символ «О» (а большое -потому что в верхнем регистре). «О-большое» определяет время выполнения в худшем случае. Предположим, вы используете простой поиск для поиска фамилии в телефонной книге. Вы знаете, что простой поиск выполняется за время О(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте, что искомая фамилия начинается на букву («А» и этот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи - вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время О(n)? А может, он занял время O(1), потому что результат был получен с первой попытки? Простой поиск все равно выполняется за время О(n). Просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако («О-большое» описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время О(n). И это дает определенные гарантии - вы знаете, что простой поиск никогда не будет работать медленнее О(n). 13 Типичные примеры «О-большого» Ниже перечислены пять разновидностей «О-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения: • O(log n ), или логарифмическое время . Пример: бинарный поиск. • О(n), или линейное время. Пример: простой поиск. • О(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка). • О(n 2 ). Пример: медленные алгоритмы сортировки (сортировка выбором). • О(n!). Пример: очень медленные алгоритмы (задача о коммивояжере). Существуют и другие варианты времени выполнения, но эти пять встречаются чаще всего. Помните, что эта запись является упрощением. На практике «О- большое» не удается легко преобразовать в количество операций с такой точностью, но пока нам хватит и этого. А пока перечислим основные результаты: 14 • Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций. • По сути, формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных. • Время выполнения алгоритмов выражается как «О-большое». • Время выполнения O(log n) быстрее О(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее. Расчет сложности. Отбрасывание констант и несущественной части Важным момент является, то, что «О-большое» указывает на самую быстро растущую сложность и отбрасывает константные оптимизации. Приведем пример функции, где рассматриваются 2 цикла, идущие друг за другом. Т.е. у нас есть n операций, а затем еще n операций. void calcArray( int * array , int n ) { int sum = 0; int p = 1; for ( int i = 0; i < n ; i++) sum += array [i]; for ( int i = 0; i < n ; i++) p *= array [i]; cout << "sum=" << sum << endl; cout << "P=" << p << endl; } Т.е. у нас есть n операций, а затем еще n операций, таким образом сложность будет О(2n). Представим, что n=∞, тогда не будет иметь значения сколько у нас будет бесконечностей – 2 или 1. Вывод. При расчете «О- большое» отбрасываются все константы. Рассмотрим, еще один пример. void calcArray( int * array , int n ) { for ( int i = 0; i < n ; i++) cout << array [i] << endl; for ( int i = 0; i < n ; i++) for ( int j = 0; j < n ; j++) array [i]= array [i]+ array [j]; } В этом примере есть один цикл (n-операций) и два вложенных цикла (n 2 - операций). Тогда логично чтобы была сложность O(n+n 2 ), то n – отбрасывают, 15 т.к. график такой сложности растет в разы медленнее n 2 . И получается сложность O(n 2 ). Data Operation O(n) 10 000 10 000 O(n 2 ) 10 000 100 000 000 Примеры «О-большое» O(n 2 +n)→O(n 2 ) O(n+logn)→O(n) O(60*2 n +10*n 100 ) →O(2 n +n 100 ) →O(2 n ) O(n 2 +m) → O(n 2 +m) int count( int n ) { int sum = 0; for ( int i = 0; i < n ; i++) for ( int j = 0; j < n ; j++) for ( int k = 0; k < 100000; k++) sum += i + j + k; return sum; } O(n*n*100 000) →O(n 2 ) int iterate( int n ) { int sum = 0; for ( int i = 0; i < n ; i++) for ( int j = i; j < n ; j++) sum += i + j; return sum; } Пусть n=4, тогда i=0, внутренний цикл сделает 4 операции i=1, внутренний цикл сделает 3 операции i=2, внутренний цикл сделает 2 операции i=3, внутренний цикл сделает 1 операцию 𝑂 ( 𝑛 2 2 ) →O(n 2 ) Сложность встроенных методов void delete_chisla(string s ) 16 { for ( unsigned int i=0; i< s .length();i++) if ( s [i] >= '0' && s [i] <= '9' ) { s .erase(i, 1); i--; } } O(n 2 ) void find_question(string s ) { for ( unsigned int i = 0; i < s .length(); i++) if ( s .find( '?' ) != string::npos) cout << i << endl; } Плохой код! Какая же сложность у данного примера? 17 Складывать или умножать? Рассмотрим примеры: for ( int i = 0; i < n; i++) cout << a[i]; for ( int j = 0; j < m; j++) cout << b[j]; В этом фрагменте кода перебираются два цикла, которые не зависят друг от друга, при этом один производит n-операций, а второй m-операций. Тогда сложность данного алгоритма O(n)+O(m). Последовательность действий – сложение. for ( int i = 0; i < n; i++) for ( int j = 0; j < m; j++) cout << a[i]+ b[j]<< endl; В этом примере, один цикл вложен в другой цикл. Тогда сложность данного алгоритма O(n*m). Выполнить что-то N-раз, пока делаешь что-то свое – умножение. 18 Анализ поиска максимального элемента в массиве Рассмотрим теперь примеры алгоритмов, оценка которых зависит не только от размерности входных данных. Наилучший случай Наихудший случай (1) max = a[0]; 1 1 (2) for ( int i = 1; i N (3) if (a[i]>max) n-1 n-1 (4) max = a[i]; 0 n-1 Нахождение оценок 1, 2 и 3 операторов не должно вызвать затруднений. А вот количество выполнений 4 оператора зависит от конкретных значений компонентов массива, поэтому мы не можем дать однозначной оценки. В этом случае поступают следующим образом. Дают не одну оценку, а три: наилучшую, наихудшую и среднюю. Из этих трех оценок сложнее всего найти среднюю (даже сформулировать что значит средняя), хотя она с практической точки зрения и является наиболее важной. Это, пожалуй, является трудно разрешимой задачей, поэтому мы ее рассматривать не будем. Что касается наилучшей и наихудшей оценок, то их искать проще. Надо представить себе такие входные данные, для которых соответствующий оператор будет выполняться наименьшее и наибольшее количество раз соответственно. Для примера наилучшими входными данными будет такой массив, в котором максимум стоит на первом месте. В этом случае 4 оператор ни разу не выполнится, так как условие в 3 операторе будет все время false. Наихудшими входными данными будет такой массив, в котором компоненты упорядочены по возрастанию. В этом случае условие в 3 операторе каждый раз будет true, и оператор 4 будет выполняться каждый раз. Таким образом, лучшая оценка нашего алгоритма равна 2n, а худшая – 3n-1. 19 Анализ алгоритма сортировки выбором Суть его в следующем. Во всем массиве ищется минимум и ставится на первое место, в оставшейся части массива ищется минимум и ставится на второе место и так далее, пока не рассмотренным не останется последний элемент массива. Этот алгоритм используют люди в повседневной жизни. Априори этот алгоритм кажется достаточно «плохим», то есть не эффективным. Рассмотрим этот алгоритм подробнее: Наилучший случай Наихудший случай (1) for ( int i = 0; i < n - 1; i++) n n (2) { lowindex = i; n-1 n-1 (3) lowkey = a[i]; n-1 n-1 (4) for ( int j=i+1; j 2 +n-2)/2 (n 2 +n-2)/2 (5) if (a[j] < lowkey) (n 2 -n)/2 (n 2 -n)/2 (6) { lowkey = a[j]; 0 (n 2 -n)/2 (7) lowindex = j; } 0 (n 2 -n)/2 (8) temp = a[i]; n-1 n-1 (9) a[i] = a[lowindex]; n-1 n-1 (10) a[lowindex] = temp; } n-1 n-1 Оценка 4 оператора получена следующим образом. Этот заголовок цикла выполняется для каждого i, причем для i =0 он выполнится n раз, для i =1 −n−1 раз, и так далее, при i=n−2−3 раза, при i = n−1−2 раза. То есть мы имеем арифметическую прогрессию a 1 ,a 2 , … ,a m , сумма которой 𝑠 𝑚 = (𝑎 1 +𝑎 𝑚 ) 2 ⋅ 𝑚 Здесь m=n−1, a 1 =n, a n-1 =2 и сумма равна (n+2)(n-1)/2 = (n 2 +n−2)/2. Оценка 5 оператора получена подобным же образом, только не надо забывать о том, что заголовок цикла for всегда выполняется на один раз больше, чем его тело. Здесь m=n-1, a 1 =n-1, a n-1 =1 и сумма равна (n−1+1)(n−1)/2 = (n 2 −n)/2. Что касается оценки 5 и 6 операторов, то с этим мы уже 20 сталкивались ранее. В зависимости от входных данных эти операторы могут выполняться различное количество раз. Для «хороших» данных (массив уже упорядочен) эти операторы не выполнятся ни разу. Для «плохих» данных эти операторы будут выполняться при каждой проверке min>a[j]. Для алгоритмов сортировки «плохие» данные представляют собой массив, упорядоченный в обратном порядке. Таким образом, лучшая оценка алгоритма «сортировки методом выбора» равна n 2 +6n−6, худшая оценка равна 2n 2 +5n−6. Плохо это, или хорошо? Пока можно заметить только, что алгоритм тратит достаточно много времени, когда массив уже упорядочен. Это несомненный минус этого алгоритма 21 Оценка алгоритмов, количество итераций которых не задано явно Рассмотрим следующую задачу: вычислить сумму бесконечного сходящегося ряда 1 + 𝑥 1! + 𝑥 2 2! + ⋯ + 𝑥 𝑛 𝑛! . Легко видеть, что это разложение в ряд широко известной экспоненциальной функции (ⅇ 𝑥 ). Ряд сходящийся, то есть каждое очередное слагаемое должно быть меньше по абсолютной величине предыдущего. Это значит, что всегда найдется такое слагаемое, начиная с которого все остальные будут добавлять к сумме пренебрежимо малую величину. Таким образом, мы можем написать алгоритм, вычисляющий искомую сумму с любой заданной точностью. Например, если заданная точность 0,01, то все слагаемые, значения которых меньше 0,01, мы отбросим, и наша вычисленная сумма будет отличаться от истинной не больше чем на 0,01. Для решения этой задачи можно составить два алгоритма. Первый представляет собой «лобовое» решение. Степень и факториал вычисляются явно: y = 0; p = 1; n = 1; while (fabs(p) <= eps) { y += p; f = 1; for ( int i = 1; i < n; i++) f *= i; p = pow(x, n) / f; n = n + 1; } Второй алгоритм более «хитрый». Он учитывает тот факт, что для того, чтобы получить второе слагаемое, достаточно первое слагаемое умножить на х и разделить на 1. Для того чтобы получить третье слагаемое достаточно второе слагаемое умножить на х и разделить на 2, и так далее. y = 0; p = 1; n = 1; 22 while (fabs(p) <= eps) { y += p/n; p *= x; n = n + 1; } Даже на первый взгляд второй алгоритм кажется более эффективным, чем первый. Давайте оценим это точно. При оценке подобных алгоритмов мы сталкиваемся с одной проблемой. Дело в том, что мы не можем знать заранее, сколько раз будет выполняться тело цикла в этом алгоритме. Мы не можем вычислить это по заданной точности eps, все зависит от конкретного ряда. Проблема кажется трудно разрешимой, однако заметим, что в обоих алгоритмах для одинаковых входных данных циклы выполняются одинаковое количество раз. А так как нам надо лишь выяснить во сколько раз один алгоритм эффективнее другого, то можно просто задать какое-либо абстрактное количество итераций цикла. Тогда алгоритмы будут выглядеть так. Первый алгоритм: y = 0; p = 1; for ( int n = 1; n < m; n++) { y += p; f = 1; for ( int i = 1; i < n; i++) f *= i; p = pow(x, n) / f; } Второй алгоритм: y = 0; p = 1; for ( int n = 1; n < m; n++) { y += p/n; p *= x; } Оценим первый алгоритм: y = 0; 1 p = 1; 1 for ( int n = 1; n < m; n++) { m+1 23 y += p; m f = 1; m for ( int i = 1; i < n; i++) (m 2 +3m)/2 f *= i; (m 2 +m)/2 p = pow(x, n) / f; } m Суммарная оценка: m 2 +6m+3. Оценка достаточно грубая, в частности мы не учитываем тот факт, что умножение требует больше времени, чем сложение, а возведение в степень – больше, чем умножение. Оценим второй алгоритм: y = 0; 1 p = 1; 1 for ( int n = 1; n < m; n++) { m+1 y += p/n; m p *= x; } m Суммарная оценка: 3m+3 Даже с учетом того, что мы проигнорировали разницу в выполнении операций возведения в степень (первый алгоритм) и умножения (второй алгоритм), второй алгоритм является гораздо более эффективным. Например, при m=10 оценка первого алгоритма 163, а второго 33. То есть, второй алгоритм выполнится почти в пять раз быстрее. При m=20 эти оценки равны 523 и 63 соответственно. Второй алгоритм быстрее почти в девять раз. 24 Анализ рекурсивных алгоритмов Рассмотрим рекурсивный алгоритм, вычисляющий сумму компонентов одномерного массива. int sum( int * a , int n ) { if (n < 0) return 0; else return sum(a, n - 1) + a[n - 1]; } Основная операция – суммирование. При изменении аргумента на 1 количество выполненных основных операций равно 1. При значении аргумента равным 0 (n<1), количество выполненных основных операций равно 0. Таким образом, мы получаем следующее рекуррентное соотношение S(n) = S(n−1) + 1, с начальным условием S(0) = 0. Решаем это рекуррентное соотношение методом обратной подстановки. Прямая подстановка: S(n−1) = S(n−2) + 1 S(n−2) = S(n−3) + 1 S(n−3) = S(n−4) + 1 … и т. д. Теперь подставляем найденные значения обратно в исходное соотношение: S(n) = (S(n−2) + 1) + 1 = ((S(n−3) + 1) + 1) + 1 = (((S(n−4) + 1) + 1) + 1) + 1) = S(n−4) + 4 Или в общем виде, для произвольного k: S(n) = S(n−k) + k. Для того, чтобы воспользоваться начальными условиями, аргумент у S в правой части должен быть равным 0. То есть, n−k = 0. Отсюда k = n. S(n) = S(n−k) + k = S(n−n) + n = S(0) + n = 0 + n = n Оценка эффективности нашего алгоритма по времени – O(n). Рекурсивный алгоритм нахождения наибольшего значения среди компонентов одномерного массива. int max( int * a , int n ) { 25 if (n <= 1) return a[n]; else if (max(a, n - 1) > a[n]) return max(a, n - 1); else return a[n]; } Основная операция – сравнение (max(a, n-1)>a[n]). Заметим, что время работы нашего алгоритма зависит не только от размерности, поэтому будем строить худшую оценку C w В худшем случае, при изменении значения размерности на 1, задача распадается на две, меньшей размерности, плюс одно сравнение. Получаем следующее рекуррентное соотношение: C w (n) = 2 ⋅ C w (n−1) + 1, с начальным условием: C w (1) = 0. Решаем рекуррентное соотношение методом обратной подстановки Прямая подстановка: C w (n−1) = 2⋅ C w (n−2) + 1 C w (n−2) = 2⋅ C w (n−3) + 1 C w (n−3) = 2⋅ C w (n−4) + 1 … и т. д. Теперь подставляем найденные значения обратно в исходное соотношение: C w (n) = 2 ⋅(2⋅C w (n−2) + 1) + 1 = = 2 ⋅(2⋅(2⋅C w (n−3) + 1) + 1) + 1 = = 2 ⋅(2⋅(2⋅(2⋅C w (n−4) + 1) + 1) + 1) + 1 == 2 4 ⋅C w (n−4) +2 3 + 2 2 + 2 1 + 2 0 Или в общем виде, для произвольного k: C w (n) = 2 k ⋅C w (n−k) +2 k-1 + 2 k-2 + … + 2 1 + 2 0 Для того, чтобы воспользоваться начальными условиями, аргумент у C w в правой части должен быть равным 1. То есть, n−k = 1. Отсюда k = n−1. C w (n) = 2 k ⋅C w (1) +2 n-2 + 2 n-3 + … + 2 1 + 2 0 C w (1) = 0, таким образом 26 C w (n) = 2 n-2 + 2 n-3 + … + 2 1 + 2 0 В правой части – сумма степеней 2: 2 n-2 + 2 n-3 + … + 2 1 + 2 0 = 2 n-1 − 1 C w (n) = 2 n-1 – 1 Оценка эффективности нашего алгоритма по времени - O(2 n ). Это очень «плохая» оценка. Но почему оценка именно такая? Дело в том, что в худшем случае мы два раза рекурсивно вызываем экземпляр нашего алгоритма с одним и тем же аргументом! Если его вызывать один раз, и сохранять результат, можно значительно улучшить наш алгоритм. int max( int * a , int n ) { int m; if (n <= 1) return a[n]; else { m = max(a, n - 1); if (m > a[n]) return m; else return a[n]; } } Основная операция по-прежнему – сравнение (m>a[n]). В худшем случае, при изменении значения размерности на 1, требуется один раз решить задачу меньшей размерности и выполнить одно сравнение. Получаем следующее рекуррентное соотношение: C w (n) = C w (n−1) + 1, с начальным условием: C w (1) = 0. Такое рекуррентное соотношение мы уже решали выше и знаем ответ: C w (n) = n Оценка эффективности улучшенного алгоритма по времени - O(n). План анализа эффективности рекурсивных алгоритмов 1. Выберите параметр (параметры), по которым будет оцениваться размер входных данных алгоритма. 2. Определите основную операцию алгоритма. 27 3. Проверьте, зависит ли число выполняемых основных операций только от размера входных данных, если оно зависит и от других факторов, рассмотрите при необходимости, как меняется эффективность алгоритма для наихудшего, среднего и наилучшего случаев. 4. Составьте рекуррентное соотношение, выражающее количество выполняемых основных операций алгоритма, и укажите соответствующие начальные условия. 5. Найдите решение рекуррентного уравнения или, если это невозможно, определите хотя бы его порядок роста. |