Основы анализа алгоритмов

Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Начнём приблизительно в 11:25-11:30. . 1 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Алгоритм является оптимальным, если не существует алгоритма, работающего быстрее. Пример, сортировка списка из трёх чисел. 1, 2, 4 2, 4, 1 1<2 да .1<4 да 2<4 да 2<4 да 2<1 нет 4, 2, 1 4, 2, 1 3 шага 2 шага 𝑥1 ≤ 𝑥2 𝑥1 ≤ 𝑥3 𝑥1 ≤ 𝑥3 𝑥2 ≤ 𝑥3 𝑥3 , 𝑥1 , 𝑥2 𝑥2 , 𝑥1 , 𝑥3 𝑥1 , 𝑥2 , 𝑥3 𝑥1 , 𝑥3 , 𝑥2 𝑥2 ≤ 𝑥3 𝑥2 , 𝑥3 , 𝑥1 𝑥3 , 𝑥2 , 𝑥1 2 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов N чисел → N! Перестановок (классов входных данных) Каждый уровень отличается от предыдущего в 2 раза Число узлов на уровне M равно 2М−1 Число уровней находим из 𝑁! ≤ 2𝑀−1 log 2 (𝑁!) ≤ 𝑀 − 1 тогда log 2 (𝑁!) + 1 ≤ 𝑀 log 2 𝑁! = log 2 𝑁 ∙ 𝑁 − 1 ∙ ⋯ ∙ 1 = 2 = log 2 𝑁 + log 2 𝑁 − 1 + ⋯ + log 2 1 ≈ 𝑁log 2 𝑁 M= 𝑁log 2 𝑁+1=5,7≈5 𝟑 𝟏 𝟒 . 4 𝟐 3 N!=3!=1*2*3=6 1 5 𝟓 𝟔 3 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Рекуррентные соотношения Формы записи: 4, 𝑇 𝑛 = 4𝑇 если 𝑛 ≤ 4 𝑛 − 1, если 𝑛 > 4 2 или 𝑛 𝑇 𝑛 = 4𝑇 −1 2 𝑇 𝑇 𝑇 𝑇 4 3 2 1 =4 =4 =4 =4 4 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Рекуррентные соотношения 𝑇 𝑛 = 4𝑇 𝑛 2 𝑛 𝑇 4 𝑛 𝑇 8 𝑛 𝑇 16 𝑇 𝑛 2 − 1; 𝑇 4 = 4; 𝑛 −1 4 𝑛 = 4𝑇 −1 8 𝑛 = 4𝑇 −1 16 𝑛 = 4𝑇 −1 32 = 4𝑇 𝑇 3 =4; 𝑇 2 =4; 𝑇 1 =4 𝑛 𝑛 𝑛 − 1 = 4 4𝑇 − 1 − 1 = 16𝑇 −5= 2 4 4 𝑛 𝑛 = 16 4𝑇 − 1 − 5 = 64𝑇 − 13 = ⋯ = 8 8 𝑇 𝑛 = 4𝑇 𝑇 𝑛 = 4𝑚−1 ∙ 4𝑇 𝑛 −( 2 4𝑚−3 ) 5 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Рекуррентные соотношения 𝑇 𝑛 = 4𝑇 𝑛 2 𝑇 𝑛 = 4𝑚−1 ∙ 4𝑇 n=8: 𝑇 8 = 4𝑇 n/2=4→n=8 𝑇 4 = 4; − 1; 8 2 𝑛 2𝑚 𝑇 3 =4; 𝑇 2 =4; 𝑇 1 =4 − ( 4𝑚−3 ) − 1 = 4𝑇 4 − 1 = 4 ∗ 4 − 1 = 15 9 n=9: 𝑇 9 = 4𝑇 − 1 = 4𝑇 4,5 − 1 = 4 ∗ 4 ∗ 4 − 1 − 1 = 43 − 41 − 1 2 16 n=16: 𝑇 16 = 4𝑇 − 1 = 4𝑇 8 − 1 = 4 ∗ 4 ∗ 4 − 1 − 1 = 43 − 41 − 1 2 17 n=17: 𝑇 17 = 4𝑇 − 1 = 4𝑇 8,5 − 1 = 4 ∗ 4 ∗ 𝑇 4,25 − 1 − 1 2 = 4 ∗ 4 ∗ 4 ∗ 4 − 1 − 1 − 1 = 44 − 42 − 41 − 1 6 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Рекуррентные соотношения 𝑇 𝑛 = 4𝑇 𝑛 2 𝑇 𝑛 = 4𝑚−1 ∙ 4𝑇 𝑇 4 =𝑇 𝑇 4 = 4; − 1; 𝑛 2𝑚 𝑛 2log2(𝑛−3) 𝑇 𝑛 = 4log2 𝑛−3 −1 𝑇 9 = 4log2 6 𝑇 17 = 4log2 𝑇 2 =4; 𝑇 1 =4 − ( 4𝑚−3 ) 4 =𝑇 2log2(4−3) ∙ 4𝑇 4 − ( ∙𝑇 4 −( 14 𝑇 3 =4; =𝑇 2log2(1) =𝑇 log2 𝑛−3 −1 𝑖 4 )=4log2 𝑛−3 𝑖=0 log2 6 −1 𝑖 4 )=42 𝑖=0 ∙𝑇 4 −( 4 ∙4−( log2 14 −1 𝑖 3 4 )=4 𝑖=0 4 20 ∙𝑇 4 −( 2 −1 𝑖 3 𝑖=0 4 )=4 ∙4−( log2 𝑛−3 −1 𝑖 4) 𝑖=0 −1−4 3 −1 𝑖 3 𝑖=0 4 )=4 − 1 − 4 − 42 7 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Рекуррентные соотношения 𝑇 𝑛 = 4𝑇 𝑛 2 − 1; 𝑇 4 = 4; 𝑇 3 =4; 𝑇 2 =4; 𝑇 1 =4 Подставим начальные условия и приведем к замкнутому виду 𝑇 𝑛 = 4log2 𝑛−3 𝑇 𝑛 = 4log2 ∙𝑇 4 −( 𝑛−3 +1 −( log2 𝑛−3 −1 𝑖 4) 𝑖=0 log2 𝑛−3 −1 𝑖 4) 𝑖=0 При желании можно дальше упростить это выражение путем разложений в ряд и эквивалентных преобразований. 8 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Последовательный поиск Алгоритм последовательного поиска последовательно просматривает по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. 1 𝐴 𝑁 = 𝑁 𝑁 𝑖=1 1 𝑁 𝑁+1 𝑁+1 𝑖= ∙ = 𝑁 2 2 1 𝐴 𝑁 = ( 𝑁+1 𝑁 𝑖=1 𝑁+2 𝑖 + 𝑁) ≈ 2 У алгоритма последовательного поиска два наихудших случая. В первом случае целевой элемент стоит в списке последним. Во втором его вовсе нет в списке. 9 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Двоичный поиск При сравнении целевого значения со средним элементом отсортированного списка возможен один из трёх результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях можем отбросить половину списка. 𝐴 𝑁 ≈ log 2 𝑁 + 1 − 1 𝐴 𝑁 ≈ log 2 𝑁 + 1 − 1/2 Анализ алгоритма двоичного поиска выполняется через дерево решений (метод турниров). 10 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Многочлены Вычисление значений многочленов вида: 𝑝 𝑥 = 𝑎𝑛 𝑥 𝑛 + 𝑎𝑛−1 𝑥 𝑛−1 + 𝑎𝑛−2 𝑥 𝑛−2 + ⋯ + 𝑎1 𝑥 1 + 𝑎0 В цикле for содержится два умножения, которые выполняются n-1 раз. Одно умножение выполняется перед циклом, поэтому общее число умножений равно 2n-2+1=2n-1. В цикле выполняется также одно сложение, и одно сложение выполняется перед циклом, поэтому общее число сложений равно n-1+1=n. Общее количество: 3n-1 11 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Многочлены Вычисление по схеме Горнера для многочлена вида: 𝑝 𝑥 =((…((𝑎𝑛 𝑥 + 𝑎𝑛−1 )𝑥 + 𝑎𝑛−2 )𝑥 + ⋯ + 𝑎1 )𝑥 + 𝑎0 Цикл выполняется n раз, причем внутри цикла есть одно умножение и одно сложение. Поэтому вычисление по схеме Горнера требует n умножений и n сложений. Общее количество: 2n 12 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Многочлены Результат можно улучшить, если обработать коэффициенты многочлена до начала работы алгоритма. Основная идея состоит в том, чтобы выразить многочлен через многочлены меньшей степени: 𝑝 𝑥 = 𝑥 𝑗 + 𝑏 𝑞 𝑥 + 𝑟 𝑥 , 𝑗 = 2𝑘−1 В обоих многочленах q и r будет вдвое меньше членов, чем в р. 13 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Многочлены Пример Дано 𝑝 𝑥 = 𝑥 7 + 4𝑥 6 − 8𝑥 4 + 6𝑥 3 + 9𝑥 2 + 2𝑥 − 3 Сначала определим 𝑥 𝑗 + 𝑏 . Степень многочлена p равна 7, т. е. 23 − 1 = 8 − 1 = 7 → 𝑘 = 3 𝑗 = 2𝑘−1 = 23−1 = 22 = 4 Теперь выберем b по правилу 𝑏 = 𝑎𝑗−1 − 1 = 𝑎4−1 − 1 = 𝑎3 − 1 = 6 − 1 = 5 14 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Многочлены Пример Найдём q и r из 𝑥 7 + 4𝑥 6 − 8𝑥 4 + 6𝑥 3 + 9𝑥 2 + 2𝑥 − 3 = 𝑥 4 + 5 𝑞 𝑥 + 𝑟(𝑥), то есть p 𝑥 = 𝑥 4 + 5 𝑥 3 + 4𝑥 2 + 0𝑥 1 + 8 + 𝑥 3 − 11𝑥 2 + 2𝑥 1 − 37 15 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Многочлены Пример Аналогично делаем с q и r 𝑞 𝑥 = 𝑥 2 − 1 𝑥 + 4 + 𝑥 + 12 𝑟 𝑥 = 𝑥 2 + 1 𝑥 − 11 + (𝑥 − 26) В итоге получаем p 𝑥 = 𝑥4 + 5 𝑥 2 − 1 𝑥 + 4 + 𝑥 + 12 + 𝑥 2 + 1 𝑥 − 11 + (𝑥 − 26) 16 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Многочлены Число операций для многочлена степени 7 Число операций для многочлена степени N 17 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Умножение матриц Стандартный алгоритм умножения Алгоритм умножения по Винограду 18 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Умножение матриц Если посмотреть на результат умножения двух матриц, то видно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц. Можно заметить также, что такое умножение допускает предварительную обработку, позволяющую часть работы выполнить заранее. 𝑉 = (𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 ) Исходные вектора 𝑊 = (𝑤1 , 𝑤2 , 𝑤3 , 𝑤4 ) 𝑉 ∙ 𝑊 = 𝑣1 𝑤1 +𝑣2 𝑤2 +𝑣3 𝑤3 +𝑣4 𝑤4 Перепишем выражение в другом виде 𝑉 ∙ 𝑊: 𝑉 ∙ 𝑊 =(𝑣1+𝑤2 )(𝑣2 +𝑤1 )+(𝑣3 +𝑤4 )(𝑣4 +𝑤3 )-𝑣1 𝑣2 -𝑣3 𝑣4 -𝑤1 𝑤2 -𝑤3 𝑤4 19 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Численные алгоритмы. Умножение матриц Алгоритм Штрассена работает с квадратными матрицами. Он настолько эффективен, что иногда разумно расширить матрицы до квадратных, и при этом он все равно дает выигрыш, превышающий расходы на введение дополнительных элементов. Формулы Штрассена: 𝑥1 = (𝐺1,1 +𝐺2,2 ) (𝐻1,1 +𝐻2,2 ) 𝑥2 = (𝐺2,1 +𝐺2,2 ) (𝐻1,1 ) 𝑥3 = (𝐺1,1 ) (𝐻1,1 −𝐻2,2 ) 𝑥4 = (𝐺1,1 ) (𝐻1,2 −𝐻2,2 ) 𝑥5 = (𝐺1,1 +𝐺2,2 ) (𝐻2,2 ) 𝑥6 = (𝐺2,1 −𝐺1,1 ) (𝐻1,1 +𝐻1,2 ) 𝑥7 = (𝐺2,1 −𝐺2,2 ) (𝐻2,1 +𝐻2,2 ) 𝑅1,1 = 𝑥1 + 𝑥4 −𝑥5 +𝑥7 𝑅2,1 = 𝑥2 + 𝑥4 𝑅1,2 = 𝑥3 + 𝑥5 𝑅2,2 = 𝑥1 + 𝑥3 − 𝑥2 +𝑥6 20 Математическая логика и теория алгоритмов Лекция № 12. Основы анализа алгоритмов Всем спасибо, все свободны) 21