Анализ эффективности алгоритмов

Список основной литературы 1. [CLRS] Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. – 3-е изд. – М.: Вильямс, 2013. 2. [Levitin] Левитин А.В. Алгоритмы: введение в разработку и анализ. – М.: Вильямс, 2006. – 576 с. 3. [Aho] Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы. – М.: Вильямс, 2001. – 384 с. 4. [DSABook] Курносов М.Г. Введение в структуры и алгоритмы обработки данных. Новосибирск: Автограф, 2015. - 179 с. Список дополнительной литературы 1. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. - М.: МЦНМО, 2014. - 320 с. 2. Кормен Т.Х. Алгоритмы: Вводный курс. - М.: Вильямс, 2014. - 208 с. 3. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. – К.: ДиаСофт, 2001. – 688 с. 4. Макконнелл Дж. Основы современных алгоритмов. – 2-е изд. – М.: Техносфера, 2004. – 368 с. 5. Скиена С.С. Алгоритмы. Руководство по разработке. – 2-е изд. – СПб: БХВ, 2011 – 720 с. 6. Керниган Б.В., Пайк Р. Практика программирования. – СПб.: Невский Диалект, 2001. – 381 с. 7. Кнут Д. Искусство программирования. Том {1, 3}, 3-е изд. - М.: Вильямс, 2010. Анализ эффективности алгоритмов Лекция 1 Решение задачи на ЭВМ 1. Постановка задачи (problem statement) – точная формулировка условий задачи с описанием её входных и выходных данных 2. Разработка алгоритма решения задачи 3. Доказательство корректности алгоритма и анализ его эффективности 4. Реализация алгоритма на языке программирования 5. Выполнение программы для получения требуемого результата Алгоритм ▪ Алгоритм (algorithm) – это конечная последовательность инструкций исполнителю, в результате выполнения которых обеспечивается получение из входных данных требуемого выходного результата (решение задачи) ▪ Уточнения ✓ Алгоритм должен описываться на формальном языке исполнителя, исключающем неоднозначность толкования предписаний ✓ Множество инструкций исполнителя конечно ✓ Запись алгоритма на формальном языке называется программой (program) Свойства алгоритма ▪ Дискретность – алгоритм представляется как последовательность инструкций исполнителя. Каждая инструкция выполняется только после того, как закончилось выполнение предыдущего шага ▪ Конечность (результативность) – алгоритм должен заканчиваться после выполнения конечного числа инструкций ▪ Массовость – алгоритм решения задачи должен быть применим для некоторого класса задач, различающихся лишь значениями входных данных ▪ Детерминированность (определенность) – каждый шаг алгоритма должен быть точно определен – записан на формальном языке исполнителя. Детерминированность обеспечивает одинаковость результата, получаемого при многократном выполнении алгоритма на одном и том же наборе входных данных Задача поиска максимального элемента ▪ вход: последовательность из n чисел (a1, a2, …, an ) ▪ выход: номер i элемента ai , имеющего наибольшее значение: 𝑎𝑖 ≥ 𝑎𝑗 , ∀𝑗 ∈ 1, 2, … , 𝑛 . Массив a [0:24]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 180 155 193 176 159 169 172 195 201 160 167 180 177 174 179 187 166 193 183 175 169 170 157 199 187 Задача поиска максимального элемента ▪ вход: последовательность из n чисел (a1, a2, …, an ) ▪ выход: номер i элемента ai , имеющего наибольшее значение: 𝑎𝑖 ≥ 𝑎𝑗 , ∀𝑗 ∈ 1, 2, … , 𝑛 . Массив a [0:24]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 180 155 193 176 159 169 172 195 201 160 167 180 177 174 179 187 166 193 183 175 169 170 157 199 187 i=8 Алгоритм линейного поиска Массив a [0:24]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 180 155 193 176 159 169 172 195 201 160 167 180 177 174 179 187 166 193 183 175 169 170 157 199 187 function Max(a[1..n]) maxi = 1 for i = 2 to n do if a[i] > a[maxi] then maxi = i end for return maxi end function Алгоритм линейного поиска Массив a [0:24]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 180 155 193 176 159 169 172 195 201 160 167 180 177 174 179 187 166 193 183 175 169 170 157 199 187 function Max(a[1..n]) maxi = 1 for i = 2 to n do if a[i] > a[maxi] then maxi = i end for return maxi end function Свойства алгоритма ✓ ✓ ✓ ✓ Дискретность Конечность Массовость Детерминированность Показатели эффективности алгоритмов ▪ Количество выполняемых операций – временная эф ф ективность (time efficiency), показывает на сколько быстро работает алгоритм ▪ Объем потребляемой памяти – пространственная эф ф ективность (space efficiency), отражает максимальное количество памяти требуемой для выполнения алгоритма ▪ Показатели эффективности позволяют: ➢ Оценивать потребности алгоритма в вычислительных ресурсах: процессорном времени, памяти, пропускной способности сети ➢ Сравнивать алгоритмы между собой Анализ времени выполнения алгоритмов ▪ Что влияет на время выполнения алгоритма (программы)? 1. Размер входных данных 2. Качество реализации алгоритма на языке программирования 3. Качество скомпилированного кода 4. Производительность вычислительной машины ▪ Для большинства алгоритмов количество выполняемых ими операций напрямую зависит от размера входных данных ▪ Например, в алгоритме поиска наибольшего элемента время выполнения определяется не значениями в массиве, а его длиной n Входные данные Алгоритм (программа) Компилятор, интерпретатор Вычислительная машина Размер входных данных алгоритма ▪ У каждого алгоритма есть параметры, определяющие размер его входных данных ➢Поиск наименьшего элемента в массиве: n – количество элементов в массиве ➢Алгоритм умножения двух матриц: количества строк m и столбцов n в матрицах ➢Сравнение двух строк: s1, s2 – длина первой и второй строк ➢Поиск кратчайшего пути в граф е между парой вершин: n, m – количество вершин и ребер в графе Количество операций алгоритма ▪ Количество операций алгоритма можно выразить как ф ункцию от размера его входных данных: T (n), T (s1, s2), T (n, m) ▪ В качестве исполнителя будем использовать модель однопроцессорной вычислительной машины с произвольным доступом к памяти ✓ Машина обладает неограниченной памятью ✓ Для выполнения арифметических и логических операций (+, ‒, *, /, %) требуется один временной шаг – такт процессора ✓ Обращение к оперативной памяти для чтения или записи занимает один временной шаг ✓ Выполнение условного перехода (if-then-else) требует вычисления логического выражения и выполнения одной из ветвей if-then-else ✓ Выполнение цикла (for, while, do) подразумевает выполнение всех его итераций Суммирование элементов массива function SumArray(a[1..n]) sum = 0 for i = 1 to n do sum = sum + a[i] end for return sum end function ▪ Время работы алгоритма SumArray зависит только от размера n массива ▪ Выразим число T (n ) операций, выполняемых алгоритмом Суммирование элементов массива function SumArray(a[1..n]) sum = 0 // for i = 1 to n do // sum = sum + a[i] // end for return sum // end function Запись в память i <= n, jle, i++ 2 чтения, +, запись Возврат значение 1 оп. ▪ Выразим число T (n) операций, выполняемых алгоритмом T (n ) = 1 + 4 n + 1 = 4 n + 2 ▪ Можно ограничиться подсчётом только базовых операций – наиболее важных операций, от которых зависит время выполнения алгоритма ▪ В алгоритме SumArray – это операция «+» Линейный поиск элемента в массиве function LinearSearch(a[1..n], x) for i = 1 to n do if a[i] == x then return i end for return -1 end function ▪ Количество операций алгоритма LinearSearch может существенно отличаться для одного и того же размера n входных данных ▪ Базовая операция алгоритма – это сравнение a[i] = x ▪ Рассмотрим три возможных случая: ✓ Лучший случай (best case) ✓ Худший случай (worst case) ✓ Средний случай (average case) Линейный поиск элемента в массиве function LinearSearch(a[1..n], x) for i = 1 to n do if a[i] == x then return i end for return -1 end function LinearSearch(a[], 6, 45) 1 2 3 4 5 6 45 21 93 4 22 67 ▪ Лучший случай (best case) – это экземпляр задачи (набор входных данных), на котором алгоритм выполняет наименьшее число операций ▪ Для LinearSearch – это входной массив, первый элемент которого содержит искомое значение x (одно сравнение) 𝑇𝐵𝑒𝑠𝑡 𝑛 = 1 Линейный поиск элемента в массиве function LinearSearch(a[1..n], x) for i = 1 to n do if a[i] == x then return i end for return -1 end function LinearSearch(a[], 6, 67) 1 2 3 4 5 6 45 21 93 4 22 67 ▪ Худший случай (worst case) – это экземпляр задачи, на котором алгоритм выполняет наибольшее число операций ▪ Для LinearSearch – это массив, в котором отсутствует искомый элемент или он расположен в последней ячейке (n сравнений) 𝑇𝑊𝑜𝑟𝑠𝑡 𝑛 = 𝑛 Линейный поиск элемента в массиве function LinearSearch(a[1..n], x) for i = 1 to n do if a[i] == x then return i end for return -1 end function LinearSearch(a[], 6, x) 1 2 3 4 5 6 45 21 93 4 22 67 ▪ Средний случай (average case) – это “средний” экземпляр задачи, набор “усреднённых” входных данных ▪ В среднем случае оценивается математическое ожидание количества операций, выполняемых алгоритмом ▪ Не всегда очевидно, какие входные данные считать «усреднёнными» для задачи Линейный поиск элемента в массиве ▪ Обозначим через p ∈ [0, 1] вероятность присутствия искомого элемента x в массиве ▪ Будем считать, что искомый элемент с одинаковой вероятностью 𝑝/𝑛 может находится в любой из n ячеек массива ▪ В общем случае, если элемент x расположен в ячейке i, то это требует выполнения i сравнений ▪ Запишем математическое ожидание (среднее значение) числа операций, выполняемых алгоритмом 𝑇𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑝 𝑝 𝑝 𝑝 𝑛 = 1 + 2 + ⋯+ 𝑖 + ⋯+ 𝑛 𝑛 𝑛 𝑛 𝑛 Линейный поиск элемента в массиве ▪ В нашей оценке мы должны учесть и тот факт, что искомое значение x с вероятностью 1 – p может отсутствовать в массиве ▪ Тогда формула примет следующий вид 𝑇𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑝 𝑛 = 1+2 +⋯+𝑛 + 1−𝑝 𝑛 = 𝑛 𝑝 𝑛2 + 𝑛 = + 1−𝑝 𝑛 𝑛 2 𝑛+1 =𝑝 + 1−𝑝 𝑛 2 ▪ Вывод: если искомый элемент присутствует в массиве (p = 1), то в среднем требуется выполнить (n + 1) / 2 операции сравнения для его нахождения Какой случай рассматривать? ▪ При анализе алгоритмов мы будем уделять основное внимание времени работы алгоритмов в худшем случае – максимальному времени работы на всех наборах входных данных ▪ При возможности будем строить оценки эффективности для среднего случая ▪ Понятия количество операций алгоритма и время выполнения алгоритма (execution time) мы будем использовать как синонимичные Анализ сложности алгоритмов ▪ Известно количество операций, выполняемых двумя алгоритмами, решающими одну задачу: ✓ 𝑇1(𝑛) = 90𝑛2 + 201𝑛 + 2000 ✓ 𝑇2(𝑛) = 2𝑛3 + 3 • Какой из алгоритмов предпочтительнее использовать на практике? Анализ сложности алгоритмов Мы можем найти такое значение n0 при котором происходит пересечение функций T1(n ) и T2(n ), и на основе n0 отдавать предпочтение тому или иному алгоритму Анализ сложности алгоритмов ▪ Если известно, что на вход будут поступать данные небольших размеров, то вопрос о выборе эффективного алгоритма не является первостепенным – можно использовать самый “простой” алгоритм ▪ Вопросы, связанные с эф ф ективностью алгоритмов, приобретают смысл при больших размерах входных данных – при 𝒏 → ∞ T(n) 2 000 000 T2(n) = 2n3 + 3 1 750 000 1 500 000 Алгоритм 1 эффективнее Алгоритм 2 эффективнее 1 250 000 Алгоритм 1 эффективнее 1 000 000 750 000 500 000 250 000 T1(n) = 90n2 + 201n + 2000 n 1 9 17 25 33 41 n49 57 65 73 81 89 97 Скорость роста функции • Скорость роста (rate of growth) или порядка роста (order of growth) функций 𝑇(𝑛) определяется её старшим, доминирующим членом 𝟐 𝒏 𝐥𝐠 𝒏 𝐥𝐨𝐠 𝟐 𝒏 𝒏 𝒏 𝐥𝐨𝐠 𝟐 𝒏 𝒏 𝟐 𝒏! 1 1 2 1 0.3 0.5 0.6 0.7 0.78 0.85 0.90 0.95 1 3 4 5 6 1 1.6 2.0 2.3 2.6 2.8 3 3.2 3.3 10 13.3 16.6 19.9 2 3 4 5 6 7 8 9 10 1 000 10 000 100 000 1 000 000 2 5 8 12 16 20 24 29 33 9 966 132 877 1 660 964 19 931 569 4 9 16 25 36 49 64 81 100 1 000 000 100 000 000 10 000 000 000 1 000 000 000 000 4 8 16 32 64 128 256 512 1024 2 6 24 120 720 5 040 40 320 362 880 3 628 800 Скорость роста функции Пусть процессор выполняет одну операцию за 0.000000001 с (тактовая частота 1 ГГц) 𝟐 𝒏 𝐥𝐠 𝒏 𝐥𝐨𝐠 𝟐 𝒏 𝒏 𝒏 𝐥𝐨𝐠 𝟐 𝒏 𝒏 𝟐 1 1 2 1 1 1.6 2.0 2.3 2.6 2.8 3 3.2 3.3 10 13.3 16.6 19.9 2 3 4 5 6 7 8 9 10 1 000 10 000 100 000 1 000 000 2 5 8 12 16 20 24 1000 с = 29 16 мин 40 с 33 9 966 132 877 1 660 964 19 931 569 4 9 16 25 36 49 64 81 100 1 000 000 100 000 000 10 000 000 000 1 000 000 000 000 4 8 16 32 64 128 256 512 1024 2 6 24 120 720 5 040 40 320 362 880 3 628 800 0.3 0.5 0.6 0.7 0.78 0.85 0.90 0.95 1 30,001 с 4 5 6 𝒏! Анализ сложности алгоритмов ▪ Нам требуется математический аппарат, дающий ответ на вопрос какая из ф ункций растёт быстрее при 𝒏 → ∞ ✓ 𝑇1(𝑛) = 90𝑛2 + 201𝑛 + 2000 ✓ 𝑇2(𝑛) = 2𝑛3 + 3 ▪ Ответы на эти вопросы дает асимптотический анализ (asymptotic analysis), который позволяет оценивать скорость роста функций 𝑇(𝑛) при стремлении размера входных данных к бесконечности (при n → ∞) Асимптотические обозначения ▪ Как правило, функция времени 𝑇(𝑛) выполнения алгоритма имеет большое количество локальных экстремумов – неровный график с выпуклостями и впадинами ▪ Проще работать с верхней и нижней оценками (границами) времени выполнения алгоритма 140 T(n) 1,2 120 Верхняя граница T(n) 1 T(n) 0,8 80 0,6 60 0,4 40 Нижняя граница T(n) 0,2 T(n) 100 n0 Нижняя граница 20 n 1 Верхняя граница n 1 3 5 7 9 11 13 15 17 19 Асимптотические обозначения ▪ В теории вычислительной сложности алгоритмов (computational complexity theory) для указания границ функций 𝑇(𝑛) используют асимптотические обозначения: 𝑂 (о большое), Ω (омега большое), Θ (тета большое), а также 𝑜 (о малое), 𝜔 (омега малое) 140 T(n) 1,2 120 Верхняя граница T(n) 1 T(n) 0,8 80 0,6 60 0,4 40 Нижняя граница T(n) 0,2 T(n) 100 n0 Нижняя граница 20 n 1 Верхняя граница n 1 3 5 7 9 11 13 15 17 19 Асимптотические обозначения ▪ Далее будем считать, что областью определения функций 𝑓(𝑛) и 𝑔(𝑛), которые выражают число операций алгоритма, является множество неотрицательных целых чисел: 𝑛 ∈ {0, 1, 2, … } ▪ Функции 𝑓(𝑛) и 𝑔(𝑛) являются асимптотически неотрицательными – при больших значениях 𝑛 они принимают значения, большие или равные нулю O-обозначение (о большое) ▪ Пусть 𝑓(𝑛) – это количество операций выполняемых алгоритмом ▪ О-обозначение 𝑓(𝑛) = 𝑂(𝑔(𝑛)) ∃𝒄 > 𝟎, 𝒏𝟎 ≥ 𝟎: 𝒇 𝒏 ∈ 𝑶 𝒈(𝒏) = 𝟎 ≤ 𝒇 𝒏 ≤ 𝒄𝒈 𝒏 , ∀𝒏 ≥ 𝒏𝟎 ▪ Существуют константы 𝑐 > 0 и 𝑛0 ∈ {0, 1, 2, … } такие, что 1,2 𝑓(𝑛) ≤ 𝑐 ∙ 𝑔(𝑛) для всех 𝑛 ≥ 𝑛0 cg(n) ▪ Функция 𝑓(𝑛) ограничена сверху функцией 𝑔(𝑛) 0,8 с точностью до постоянного множителя 1 f(n) 0,6 ▪ Читается как “𝑓 от 𝑛 есть о большое от 𝑔 от 𝑛” 0,4 ▪ Используется чтобы показать, что время работы0,2 алгоритма растет не быстрее чем функция 𝑔(𝑛) 0 n0 1 Асимптотическая верхняя граница (asymptotic upper bound) для ф ункции 𝒇(𝒏) n O-обозначение (о большое) ▪ Докажем, что 2𝑛 – 10 = 𝑂(𝑛) ▪ Для этого требуется найти константы 𝑐 > 0 и 𝑛0 ∈ {0, 1, 2, … } ▪ Доказательство: возьмём 𝑐 = 2, 𝑛0 = 5 ▪ Эти значения обеспечивают выполнение неравенства 0 ≤ 2𝑛 – 10 ≤ 2𝑛 для любых 𝑛 ≥ 5 50 ▪ Прямая 2𝑛 проходит выше прямой 2𝑛 – 10 40 2n 30 20 f(n) = 2n – 10 10 n 1 -10 -20 3 5 n0 7 9 11 13 15 17 19 O-обозначение (о большое) ▪ 𝟑𝒏𝟐 + 𝟏𝟎𝟎𝒏 + 𝟖 = 𝑶(𝒏𝟐) Для доказательства возьмём 𝑐 = 4, 𝑛0 = 101, при любых 𝑛 ≥ 101 справедливо неравенство 0 ≤ 3𝑛2 + 100𝑛 + 8 ≤ 4𝑛2 ▪ 𝟑𝒏𝟐 + 𝟏𝟎𝟎𝒏 + 𝟖 = 𝑶(𝒏𝟑) Возьмём 𝑐 = 1, 𝑛0 = 12, для любых 𝑛 ≥ 12 справедливо 0 ≤ 3𝑛2 + 100𝑛 + 8 ≤ 𝑛3 ▪ 𝟎. 𝟎𝟎𝟎𝟎𝟎𝟏𝒏𝟑 ≠ 𝑶(𝒏𝟐) Так не существует констант 𝑐 > 0 и 𝑛0, которые обеспечивают выполнения неравенств из определения 𝑂. Так для любых 𝑐 > 0 и 𝑛 ≥ 𝑐 / 0.000001 имеет место неравенство 0.000001𝑛3 > 𝑐𝑛2 Ω-обозначение (омега большое) ▪ Пусть 𝑓(𝑛) – это количество операций выполняемых алгоритмом ▪ Ω-обозначение 𝑓(𝑛) = Ω(𝑔(𝑛)) ∃𝒄 > 𝟎, 𝒏𝟎 ≥ 𝟎: 𝒇 𝒏 ∈ Ω 𝒈(𝒏) = 𝟎 ≤ 𝒄𝒈 𝒏 ≤ 𝒇 𝒏 , ∀𝒏 ≥ 𝒏𝟎 ▪ Функция 𝑓(𝑛) ограничена снизу функцией 𝑔 𝑛 1,2 с точностью до постоянного множителя 1 0,8 ▪ Используется чтобы показать, что функция 0,6 (время работы алгоритма) растет не медленнее чем функция 𝑔(𝑛) 0,4 0,2 ▪ Читается как “𝑓 от 𝑛 есть омега большое от 𝑔 от 𝑛" n0 f(n) cg(n) 1 Асимптотическая нижняя граница (asymptotic lower bound) для ф ункции 𝒇(𝒏) n Θ-обозначения (тета большое) ▪ Пусть 𝑓(𝑛) – это количество операций выполняемых алгоритмом ▪ Θ-обозначение 𝑓(𝑛) = Θ(𝑔(𝑛)) ∃𝒄𝟏 > 𝟎, 𝒄𝟐 > 𝟎, 𝒏𝟎 ≥ 𝟎: 𝒇 𝒏 ∈ Θ 𝒈(𝒏) = 𝟎 ≤ 𝒄𝟏 𝒈 𝒏 ≤ 𝒇 𝒏 ≤ 𝒄𝟐 𝒈 𝒏 , ∀𝒏 ≥ 𝒏𝟎 ▪ Функция 𝑓(𝑛) ограничена снизу и сверху функцией 𝑔(𝑛) с точностью до постоянного множителя 1,2 c2g(n) 1 f(n) 0,8 0,6 c1g(n) 0,4 0,2 n0 1 Асимптотически точная оценка (asymptotic tight bound) для ф ункции 𝒇(𝒏) n Пример ▪ Пусть 𝑓 𝑛 = 1 2 𝑛 2 − 3𝑛 (количество операций в алгоритме) ▪ Докажем, что 𝑓 𝑛 = Θ 𝑛2 ▪ Доказательство следует из определения Θ-обозначения: ∃𝑐1 > 0, 𝑐2 > 0, 𝑛0 ≥ 0: 0 ≤ 𝑐1 𝑛2 ▪ Необходимо найти 𝒄𝟏 , 𝒄𝟐 , 𝒏𝟎 1 2 ≤ 𝑛 − 3𝑛 ≤ 𝑐2 𝑛2 , 2 ∀𝑛 ≥ 𝑛0 Пример ▪ Необходимо найти 𝒄𝟏 > 𝟎, 𝒄𝟐 > 𝟎, 𝒏𝟎 > 𝟎: 1 3 0 ≤ 𝑐1 ≤ − ≤ 𝑐2 , 2 𝑛 ∀𝑛 ≥ 𝑛0 1 3 − 2 𝑛 1,0000 0,5000 0,0000 -0,5000 -1,0000 -1,5000 -2,0000 -2,5000 -3,0000 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 1 𝑐1 = , 14 1 𝑐2 = , 2 𝑛≥7 𝑛≥1 𝒏𝟎 = 𝟕 Свойства O, Θ, Ω • 𝑶(𝒇(𝒏)) + 𝑶(𝒈(𝒏)) = 𝑶(max(𝒇(𝒏), 𝒈(𝒏))) Пример: 𝑛3 + 𝑛2 + 𝑛 + 1 = 𝑂(𝑛3) • 𝑶(𝒄 ∙ 𝒇(𝒏)) = 𝑶(𝒇(𝒏)) Пример: 𝑂(4𝑛3) = 𝑂(𝑛3) • 𝑶(𝒇(𝒏)) ∙ 𝑶(𝒈(𝒏)) = 𝑶(𝒇(𝒏) ∙ 𝒈(𝒏)) Пример: 𝑂(𝑛3) ∙ 𝑂(𝑛) = 𝑂(𝑛4) Основные классы сложности Класс сложности 𝑶(𝟏) 𝑶(log(𝒏)) 𝑶(𝒏) 𝑶(𝒏𝒍𝒐𝒈𝒏) Название Константная сложность Логарифмическая сложность Линейная сложность Линейно-логарифмическая сложность 𝑶(𝒏𝟐) Квадратичная сложность 𝑶(𝒏𝟑) Кубическая сложность 𝑶(𝟐𝒏) Экспоненциальная сложность 𝑶(𝒏!) Факториальная сложность Пространственная эффективность ▪ Какова “сложность по памяти” алгоритма сортировки методом “пузырька”? ▪ Сколько ячеек памяти требуется алгоритму (не учитывая входной массив)? function BubbleSort(v[1..n]) for i = 1 to n – 1 do for j = n to i + 1 do if v[j - 1] > v[j] then temp = v[j - 1] v[j - 1] = v[j] v[j] = temp end if end for end for end function Пространственная эффективность ▪ Какова “сложность по памяти” алгоритма сортировки методом “пузырька”? ▪ Сколько ячеек памяти требуется алгоритму (не учитывая входной массив)? function BubbleSort(v[1..n]) for i = 1 to n – 1 do for j = n to i + 1 do if v[j - 1] > v[j] then temp = v[j - 1] v[j - 1] = v[j] v[j] = temp end if end for end for end function ▪ Переменные i, j, temp занимают 3 ячейки памяти ▪ 𝑻(𝒏) = 𝟑 = 𝑶(𝟏) ▪ Константная сложность по памяти Литература ▪ Обязательное чтение ✓ [DSABook] http://dsabook.mkurnosov.net/ [Глава 1] ✓ [CLRS] “Глава 3. Рост функций” ✓ [Aho] “1.4 Время выполнения программ” ▪ Дополнительное чтение ✓ [Levitin] “Основы анализа эффективности алгоритмов”