Анализ алгоритмов. Активный обучающий подход

1. Введение
2. Основы анализа алгоритмов
3. Что такое анализ?
4. Вычислимость алгоритма на машине Тьюринга
5. Разбиение различных входных множеств на классы
6. Сложность по памяти
7. Что подсчитывать и что учитывать при анализе алгоритмов
8. Классы входных данных
9. Округление влево и вправо
10. Факториал натурального числа
11. Логарифмы
12. Бинарные деревья
13. Вероятности
14. Формулы суммирования
15. Скорости роста
16. Классификация скоростей роста
17. Метод турниров
18. Нижние границы
19. Анализ программ
20. Упражнения по анализу алгоритмов

Анализ программ

Предположим, что у нас есть большая сложная программа, которая работает медленнее, чем хотелось бы. Как обнаружить части программы, тонкая настройка которых привела бы к заметному ускорению ее работы?

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

Предположим, что в нашей программе некоторая простая подпрограмма вызывалась 50 000 раз, а каждая из сложных подпрограмм лишь однажды. Тогда нужно уменьшить число операций в сложных программах на 50 000, чтобы достичь того же эффекта, что производит удаление всего одной операции в простой подпрограмме. Понятно, что простое улучшение одной подпрограммы найти гораздо проще, чем 50 000 улучшений в группе подпрограмм.

Счетчики можно использовать и на уровне подпрограмм. В этом случае мы создаем набор глобальных счетчиков, по одному в каждой значимой точке, которую мы можем предугадать. Предположим, что мы хотим узнать, сколько раз выполняется каждая из частей then и else некоторого оператора if. Тогда можно создать два счетчика, и увеличивать первый из них при попадании в часть then, а второй — при попадании в часть else. В конце работы программы эти счетчики будут содержать интересующую нас информацию. Другими значимыми точками могут оказаться вхождения в циклы и операторы ветвления. Вообще говоря, счетчики стоит устанавливать в любых местах возможной передачи управления.

В конце работы программы установленные счетчики будут содержать информацию о числе выполнений каждого из блоков подпрограммы. Затем можно исследовать возможность улучшить те части подпрограммы, которые выполняют наибольший объем работы.

Этот процесс важен, и во многих компьютерах и системах разработки программного обеспечения есть средства автоматического получения такой информации о программах.

Нижние границы

Алгоритм является оптимальным, если любой алгоритм, решающий ту же задачу, работает не быстрее данного. 

• Как узнать, оптимален ли наш алгоритм? 
• Или, быть может, он не оптимален, но все-таки достаточно хорош? 

Для ответа на эти вопросы мы должны знать наименьшее количество операций, необходимое для решения конкретной задачи, которое называется нижней границей. Для этого следует изучать именно задачу, а не решающие ее алгоритмы. Нижняя граница определяет объем работы, необходимый для решения поставленной задачи, и показывает, что любой алгоритм, претендующий на то, что решает ее быстрее, обязан неправильно обрабатывать некоторые ситуации.

Для анализа процесса сортировки списка из трех чисел вновь воспользуемся бинарным деревом. Внутренние узлы дерева будем помечать парами сравниваемых элементов. Порядок элементов, обеспечивающий проход по данной ветви дерева, изображается в соответствующем листе дерева. Дерево для списка из трех элементов изображено на следующем рисунке. Такое дерево называется деревом решения.

Дерево решений для сортировки трехэлементного списка

Всякий алгоритм сортировки создает свое дерево решений в зависимости от того, какие элементы он сравнивает.

• Самый длинный путь в дереве решений от корня к листу соответствует наихудшему случаю. 
• Наилучшему случаю отвечает кратчайший путь. 
• Средний случай описывается частным от деления числа ребер в дереве решений на число листов в нем. 

На первый взгляд, ничего не стоит нарисовать дерево решений и подсчитать нужные числа. Представьте себе, однако, размер дерева решений при сортировке 10 чисел. Как уже говорилось, число возможных порядков равно 3 628 800. Поэтому в дереве будет по меньшей мере 3 628 800 листьев, а может и больше, поскольку к одному и тому же порядку можно прийти в результате различных последовательностей сравнений. В таком дереве должно быть не меньше 22 уровней.

Как же можно получить границы для сложности алгоритма с помощью дерева решений? Мы знаем, что корректный алгоритм должен упорядочивать любой список данных, независимо от исходного порядка элементов в нем. Для любой перестановки входных значений должен существовать по крайней мере один лист, а это означает, что в дереве решений должно быть не меньше N! листьев. Если алгоритм по-настоящему эффективен, то каждая перестановка появится в нем лишь однажды. Сколько уровней должно быть в дереве с N! листьями? Мы уже видели, что в каждом очередном уровне вдвое больше узлов, чем в предыдущем. Число узлов на уровне К равно 2^K-1, поэтому в нашем дереве решений будет L уровней, где L — наименьшее целое число, для которого N <= 2^L-1. Логарифмируя это неравенство, получаем log₂N! <= L - 1.

Можно ли избавиться от факториала, чтобы найти наименьшее значение L? Обратимся к свойствам факториала. Воспользуемся тем, что log₂N! = log₂(N(N-1)(N-2)...1), откуда в силу равенства log_b(xy) = log_bx + log_by (1.5)

.

Из равенства  (1.21) получаем

.

Это означает, что минимальная глубина L дерева решений для сортировки имеет порядок O(Nlog₂N). Теперь мы знаем, что любой алгоритм сортировки порядка O(NlogN) является наилучшим, и его можно считать оптимальным. Более того, из этого исследования вытекает, что любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно.

При выводе нижней границы для алгоритма сортировки предполагалось, что алгоритм работает путем последовательного попарного сравнения элементов списка. Существует другой алгоритмом сортировки (корневая сортировка), который требует линейного времени. Для достижения цели этот алгоритм не сравнивает значения ключей, а разбивает их на «кучки».

Метод турниров

Метод турниров основан на рекурсии, и с его помощью можно решать различные задачи, в которых информация, полученная в результате первого прохода по данным, может облегчить последующие проходы. Если мы воспользуемся им для поиска наибольшего значения, то он потребует построения бинарного дерева, все элементы которого являются листьями. На каждом уровне два элемента объединены в пару, причем наибольший из двух элементов копируется в родительский узел. Процесс повторяется до достижения корневого узла. Полное дерево турнира для фиксированного набора данных изображено на следующем рисунке:

Дерево турнира для набора из восьми значений

В упражнении 1.1.3.5 упоминался алгоритм для поиска второго по величине элемента списка из N значений, требующий около N сравнений. Метод турниров поможет нам в этом. В результате всякого сравнения мы получаем «победителя» и «проигравшего». Проигравших мы забываем, и вверх по дереву двигаются только победители. Всякий элемент, за исключением наибольшего, «проигрывает» в точности в одном сравнении. Поэтому для построения дерева турнира требуется N - 1 сравнение.

Второй по величине элемент мог проиграть только наибольшему. Спускаясь по дереву вниз, мы составляем список элементов, проигравших наибольшему. Формулы для деревьев показывают, что число таких элементов не превосходит ⌈log₂N⌉. Их поиск по дереву потребует ⌈log₂N⌉ сравнений; еще ⌈log₂N⌉ - 1 сравнений необходимо для выбора наибольшего из них. На всю работу уйдет N + 2⌈log₂N⌉ - 2, т. е. O(N) сравнений.

С помощью метода турниров можно и сортировать список значений. Сортировка кучей, основана на методе турниров.

Классификация скоростей роста

Скорость роста сложности алгоритма играет важную роль, и мы видели, что скорость роста определяется старшим, доминирующим членом формулы. Поэтому мы будем пренебрегать младшими членами, которые растут медленнее. Отбросив все младшие члены, мы получаем то, что называется порядком функции или алгоритма, скоростью роста сложности которого она является.

Алгоритмы можно сгруппировать по скорости роста их сложности: 

• алгоритмы, сложность которых растет по крайней мере так же быстро, как данная функция;
• алгоритмы, сложность которых растет с той же скоростью;
• и алгоритмы, сложность которых растет медленнее, чем эта функция.

Скорости роста

Точное знание количества операций, выполненных алгоритмом, не играет существенной роли в анализе алгоритмов. Куда более важным оказывается скорость роста этого числа при возрастании объема входных данных. Она называется скоростью роста алгоритма. Небольшие объемы данных не столь интересны, как то, что происходит при возрастании этих объемов.

Формулы суммирования

При анализе алгоритмов нам придется складывать величины из некоторых наборов величин. Пусть, скажем, у нас есть алгоритм с циклом. Если переменная цикла принимает значение 5, то цикл выполняется 5 раз, а если её значение равно 20, то двадцать. Вообще, если значение переменной цикла равно M, то цикл выполняется M раз. В целом если переменная цикла пробегает все значения от 1 до N, то суммарное число выполнений цикла равно сумме всех натуральных чисел от 1 до N. Мы записываем эту сумму в виде . В нижней части знака суммы стоит начальное значение переменной суммирования, а в его верхней части - её конечное значение. Понятно, как такое обозначение связано с интересующими нас суммами.

Если какое-нибудь значение записано в виде подобной суммы, то его зачастую стоит упростить, чтобы результат можно было сравнивать с другими подобными выражениями. Не так уж просто сообразить, какое из двух чисел больше  и .

Вероятности

Мы собираемся анализировать алгоритмы в зависимости от входных данных, а для этого нам необходимо оценивать, насколько часто встречаются те или иные наборы входных данных. Тем самым, нам придется работать с вероятностями того, что входные данные удовлетворяют тем или иным условиям. 

Вероятность того или иного события представляет собой число в интервале между нулем и единицей, причем вероятность 0 означает, что событие не произойдет никогда, а вероятность 1 - что оно произойдет наверняка. 

Если нам известно, что число различных возможных значений входа в точности равно 10, то мы можем с уверенностью сказать, что вероятность каждого такого входа заключена между 0 и 1, и что сумма всех этих вероятностей равна 1, поскольку один из них наверняка должен быть реализован. Если возможности реализации каждого из входов одинаковы, то вероятность каждого из них равна 0,1 (один из 10, или 1/10).

По большей части, наш анализ будет заключаться в описании всех возможностей, а затем мы будем предполагать, что все они равновероятны. Если общее число возможностей равно N, то вероятность реализации каждой из них равна 1/N.

Бинарные деревья

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом, или корнем.

Бинарное дерево с N узлами имеет не меньше ⌊log₂N + 1⌋ уровней (при максимально плотной упаковке узлов). 

Например, у полного бинарного дерева с 15 узлами один корень, два узла на втором уровне, четыре узла на третьем уровне и восемь узлов на четвертом уровне; наше равенство также дает ⌊log₂15⌋ + 1 = ⌊3,9⌋ + 1 = 4 уровня.

Заметим, что добавление еще одного узла к дереву приведет к необходимости появления нового уровня, и их число станет равным ⌊log₂16⌋ + 1 = ⌊4⌋ + 1 = 5.

В самом большом бинарном дереве с N узлами N уровней: у каждого узла этого дерева в точности один потомок (и само дерево представляет собой просто список) .

Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером k лежит не более чем 2^k-1 узла.

У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья (узлы без потомков) лежат на уровне с номером j, и у каждого узла на уровнях с первого по j - 1 в точности два непосредственных потомка.

В полном бинарном дереве с j уровнями 2^j - 1 узел. 

Логарифмы

Логарифмом числа x по основанию b называется такой показатель степени a, в которую нужно возвести b, чтобы получить x.

log_bx = a тогда и только тогда, когда b^a = x.

log₁₀45 приблизительно равен 1,653, поскольку 10^1,653 ≈ 45.

Основанием логарифма может служить любое положительное число, отличное от 1, однако в анализе алгоритмов чаще всего встречаются логарифмы по основаниям 10 и 2.

Логарифм - строго возрастающая функция, если его основание больше 1. Это означает, что если x > y, то log_bx > log_by для любого основания b. Логарифм - взаимно однозначная функция, т.е. если log_bx = log_by, то x = y.

Важные свойства логарифма, справедливые при положительных значениях входящих в них переменных:

• log_b1 = 0; (1.3)
• log_bb = 1; (1.4)
• log_b(xy) = log_bx + log_by; (1.5)
• log_bx^y = ylog_bx; (1.6)
• log_ax = log_bx / log_ba; (1.7)

Тождество log_ax = log_bx / log_ba позволяет менять основание логарифма.

Большинство калькуляторов позволяют вычислять логарифмы по основанию 10 и натуральные логарифмы (по основанию e).

log₄₂75 = log_e75 / log_e42 ≈ 1,155

Факториал натурального числа

Факториал натурального числа N обозначается через N! и представляет собой произведение всех натуральных чисел от 1 до N. 

Например 3! = 3 ⋅ 2 ⋅ 1 = 6, а 6! = 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 720. 

Видно, что факториал становится большим очень быстро.

Округление влево и вправо

Округлением влево (вниз) (или целой частью) числа x называется наибольшее число, не превосходящее x (обозначается ⌊x⌋).

⌊2,5⌋ = 2

⌊-7,3⌋ = -8

Округлением вправо (вверх) числа x называется наименьшее целое число, которое не меньше, чем x (обозначается через ⌈x⌉).

⌈2,5⌉ = 3

⌈-7,3⌉ = -7

Округление влево и вправо применяется, когда нужно подсчитать, сколько раз было выполнено то или иное действие, причем результат будет представлять собой частное некоторых величин.

Например, при попарном сравнении N элементов, когда первый элемент сравнивается со вторым, третий с четвертым и т.д., число сравнений будет равно ⌊N/2⌋. Если N = 10, то попарных сравнений будет 5, и ⌊10/2⌋ = ⌊5⌋ = 5. А если N = 11, то число сравнений не изменится и останется равным пяти, и ⌊11/2⌋ = ⌊5,5⌋ = 5.

Классы входных данных

Наилучший случай

Наилучшим случаем для алгоритма является такой набор данных, на котором алгоритм выполняется за минимальное время. Такой набор данных представляет собой комбинацию значений, на которой алгоритм выполняет меньше всего действий. 

Вообще, время выполнения алгоритма в наилучшем случае очень часто оказывается маленьким или просто постоянным, поэтому мы будем редко проводить подобный анализ.

Пример: Если мы исследуем алгоритм поиска, то набор данных является наилучшим, если искомое значение (целевое значение) записано в первой проверяемой алгоритмом ячейке. Такому алгоритму, вне зависимости от его сложности, потребуется одно сравнение. Заметим, что при поиске в списке, каким бы он сложным ни был, наилучший случай требует постоянного времени.

Наихудший случай

Анализ наихудшего случая чрезвычайно важен, поскольку он говорит о максимальном времени работы алгоритма. При анализе наихудшего случая необходимо найти входные данные, на которых алгоритм будет выполнять больше всего работы.

Анализ наихудшего случая дает верхние оценки для времени работы частей нашей программы в зависимости от выбранных алгоритмов.

Пример: Для алгоритма поиска подобные входные данные - это список, в котором целевое значение окажется последним из рассматриваемых или вообще отсутствует. В результате может потребоваться N сравнений.

Средний случай

1. В основе анализа среднего случая лежит определение различных групп, на которые следует разбить возможные входные наборы данных. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует разбить еще раз.
2. На втором шаге определяется вероятность, с которой входной входной набор данных принадлежит каждой группе.
3. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы.

Среднее время работы вычисляет по формуле

Несоответствие левой и правой частей формулы (левая зависит от n, а правая нет) является кажущимся: и разбиение на группы, и значение параметров p_i и t_i в правой части тоже зависят от n.

, где через n обозначен размер входных данных, через m число групп, через p_i - вероятность того, что входные данные принадлежат группе с номером i, а через t_i - время, необходимое алгоритму для обработки данных из группы с номером i.

В некоторых случаях мы будем предполагать, что вероятности попадания входных данных в каждую из групп одинаковы. Например, если групп пять, то вероятность попасть в первую группу такая же, как вероятность попасть во вторую, и т.д., то есть вероятность попасть в каждую группу равна 0,2. В этом случае среднее время работы можно либо оценить по предыдущей формуле, либо воспользоваться эквивалентной ей упрощенной формулой

, справедливой при равной вероятности всех групп.

Что подсчитывать и что учитывать при анализе алгоритмов

Решение вопроса о том, что считать, состоит из двух шагов:

1. выбирается значимая операция или группа операций;
2. выбирается какие из этих операций содержатся в теле алгоритма, а какие составляют накладные расходы или уходят на регистрацию и учёт данных.

Значимые операции:

• Сравнение. Все операторы сравнения (C/C++) считаются эквивалентными, и их учитывают в алгоритмах поиска и сортировки. 
• a == b
• a != b
• a < b
• a > b
• a <= b
• a >= b
• Арифметические операции (C/C++)
• Аддитивные операции (сложения)
• a + b
• a - b
• a++ (увеличение счетчика)
• a-- (уменьшение счетчика)
• Мультипликативные операции (умножения). Умножения работают дольше чем сложения. Алгоритмы считаются предпочтительнее других, если в них меньше умножений, даже если число сложений при этом пропорционально возрастает.
• a * b
• a / b
• a % b (взятие остатка по модулю)
• Целочисленное умножение или деление на степень двойки образуют специальный случай. Эта операция сводится к сдвигу, а последний по скорости эквивалентен сложению. Однако случаев, где эта разница существенна, совсем немного, поскольку умножение и деление на 2 встречается в первую очередь в алгоритмах типа "разделяй и властвуй", где значимую роль зачастую играют операторы сравнения.
• Логарифмы и тригонометрические функции, образуют еще одну, даже более времяёмкую, чем умножения, группу операций (обычно компьютеры вычисляют их значения с помощью разложения в ряд).

См. также:

• В чем разница между получением остатка от деления и взятия модуля? - Невероятные приключения в коде - Site Home - MSDN Blogs

Упражнения по анализу алгоритмов

1.1.3.1

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

Тут и далее в решениях вместо псевдокода будет использоваться код на каком-нибудь формальном языке программирования. При желании его легко можно преобразовать в псевдокод опустив несущественные подробности.

Алгоритм на языке программирования Си подсчитывающий количество прописных букв в текстовом файле:

#include <stdio.h>

int main(void)
{
    FILE *fp;
    int c, cnt = 0;

    fp = fopen("datafile.txt", "r");

    while ((c = fgetc(fp)) != EOF)
    {
        if (c >= 'A' && c <= 'Z')
        {
            cnt++;
        }
    }

    printf("%d\n", cnt);

    fclose(fp);

    return 0;
}

В языке программирования Си значения булевых выражений вычисляются сокращенным образом. В выражении c >= 'A' && c <= 'Z', член c <= 'Z' вычисляется только, если выражение c >= 'A' истинно.
Если считать, что булевы выражения вычисляются сокращенным образом, то число сравнений требуемых этому алгоритму находится между N и 2N. Если в текстовом файле не будет ни одной прописной буквы, то алгоритму потребуется N сравнений. Если все символы в текстовом являются прописными буквами, то алгоритму потребуется 2N сравнений.
Вообще для анализа алгоритмов это неважно считать ли число сравнений при проверке сложного условия равным 1 или 2.

Максимальное значение числа операций увеличения счетчика равно N. Если все символы в текстовом являются прописными буквами, то всего будет сделано N операцией увеличения счетчика.

Минимальное значение числа операций увеличения счетчика равно 0. Если в текстовом файле не содержится прописных букв, то не будет сделано ни одной операции увеличения счетчика.

См. также:

• getc(), fgetc(), getchar()

6 Анализ алгоритмов. Активный обучающий подход. Сложность по памяти

Все алгоритмы разделяются на такие, которым достаточно ограниченной памяти, и те, которым нужно дополнительное пространство.

При записи вещественного числа из интервала от -10 до +10, имеющего один десятичный знак после запятой большинство компьютеров потратит от 4 до 8 байтов памяти, однако если предварительно умножить число на 10, то получается целое число из интервала от -100 до +100, а для его хранения выделяется всего один байт. По сравнению с первым вариантом экономия составляет от 3 до 7 байтов. Программа, в которой сохраняется 1000 таких чисел, экономит от 3000 до 7000 байтов.

Иногда такая необходимость экономить приводит к проблемам. Например, проблема 2000-го года. Программы использующие много различных дат, экономили половину места для записи года, сохраняя значение 99 вместо 1999. Авторы программ не предполагали в 80-х годах, что их продукция доживет до 2000-го года.

Разработка маленьких программ, обеспечивающих компактное хранение данных, вновь становится актуальной в связи с распространением миниатюрных электронных устройств (карманных компьютеров и мобильных телефонов).

5 Анализ алгоритмов. Активный обучающий подход. Разбиение различных входных множеств на классы

Алгоритм поиска наибольшего элемента в списке из N элементов:

#import <Foundation/Foundation.h>

#define N 10

int main(int argc, const char * argv[])
{
    @autoreleasepool
    {
        int list[N] = {5, 6, 8, 9, 4, 2, 3, 55, 23, 1};
        
        int largest = list[0]; // largest = list [1]
        for (int i = 1; i < N; i++) // for i = 2 to N do
        {
            if (list[i] > largest) // if (list [i] > largest) then
            {
                largest = list[i]; // largest = list[i]
            } // end if
        } // end for
        
        NSLog(@"%i", largest);
    }
    return 0;
}

• Если список упорядочен в порядке убывания, то перед началом цикла будет сделано одно присваивание, а в теле цикла присваиваний не будет. 
• Если список упорядочен по возрастанию, то всего будет сделано N присваиваний (одно перед началом и N - 1 в цикле).

Поэтому чтобы не получить ложное представление об алгоритме, нужно рассматривать различные возможные множества входных значений.

Различные входные множества разбиваются на классы в зависимости от поведения алгоритма на каждом множестве.

Например, число различных расстановок 10 различных чисел в списке есть 10! = 3 628 800.
Имеется 362 880 входных множеств, у которых первое число является наибольшим; их все можно поместить в один класс.
Множеств, в которых наибольшее по величине число стоит на втором месте, 362 880. Их можно отнести к другому классу.
Видно, как будет меняться число присваиваний при изменении положения наибольшего числа от 1 до N. Все входные множества нужно разбить на N разных классов по числу сделанных присваиваний. Нужно знать количество классов и объем работы на каждом множестве класса.
Такое разбиение основывается на местоположении наибольшего значения.

Для алгоритма поиска наибольшего и наименьшего значения разбиение могло бы основываться на том, где располагаются наибольшее и наименьшее значения. В таком разбиении 90 классов.

Если классы выбраны правильно, то на всех множествах входных данных одного класса алгоритм производит одинаковое количество операций, а на множествах из другого класса это количество операций скорее всего будет другим.

4 Анализ алгоритмов. Активный обучающий подход. Вычислимость алгоритма на машине Тьюринга

Абстрактную машина Тьюринга рассматривают как эквивалент алгоритма.

При анализе подсчитывается число переходов, необходимое для решения задачи. Анализ пространственных потребностей алгоритма подразумевает подсчет числа ячеек в ленте машины Тьюринга, необходимых для решения задачи. Такого рода анализ разумен, и он позволяет правильно определить относительную скорость двух алгоритмов, однако его практическое осуществление чрезвычайно трудно и занимает много времени. Сначала нужно строго описать процесс выполнения функций перехода в машине Тьюринга, выполняющей алгоритм, а затем подсчитать время выполнения - весьма утомительная процедура.

Другой способ анализа алгоритмов предполагает, что алгоритм записан на каком-либо языке высокого уровня вроде C, C++, Java или достаточно общем псевдокоде. 

В некоторых языках программирования значения булевых выражений вычисляются сокращенным образом.

В выражении A and B, член B вычисляется только, если выражение A истинно.

В выражении A or B, член B не будет вычисляться, если выражение A истинно.

Неважно считать ли число сравнений при проверке сложного условия равным 1 или 2.

3 Анализ алгоритмов. Активный обучающий подход. Что такое анализ?

1. Сколько сравнений потребует алгоритм сортировки при упорядочении списка из N величин по возрастанию?
2. Сколько арифметических операций нужно для умножения двух матриц размером N x N?

2 Анализ алгоритмов. Активный обучающий подход. Основы анализа алгоритмов

• описание анализа алгоритма;
• объяснение принципов выбора подсчитываемых операций;
• проведение анализа в наилучшем, наихудшем и среднем случаях;
• работа с логарифмами, вероятностями и суммированием;
• описание функций θ(f), Ω(f), O(f), скорости роста и порядка алгоритма;
• использование дерева решений для определения нижней границы сложности;
• вывод формулы общего члена последовательности из простых рекуррентных соотношений.