Математический анализ нерекурсивных алгоритмов - EcsFlash/DataTypes GitHub Wiki

Общий план анализа эффективности нерекурсивных алгоритмов

1. Выберите параметр(или параметры), по которому будет оцениваться размер входных данных алгоритма.
2. Определите основную операцию алгоритма. (Как правило, она находится в наиболее глубоко вложенном внутреннем цикле алгоритма.)
3. Проверьте, зависит ли число выполняемых основных операций только от размера входных данных. Если оно зависит и от других факторов, рассмотрите при необходимости, как меняется эффективность алгоритма для наихудшего и наилучшего случаев.
4. Запишите сумму, выражающую кол-во выполняемых основных операций алгоритма.
5. Используя стандартные формулы и правила суммирования, упростите полученную формулу для кол-ва основных операций алгоритма.Если это невозможно, определите хотя бы порядок роста.

Тут важно указать 2 основных правил суммирования, которые пригодятся нам в будущем

Рассмотрим примеры задач

Пример 1. Рассмотрим задачу поиска наибольшего элемента в списке из n чисел. Пройдемся по нашему плану:

1. Размер n - кол-во элементов в массиве
2. Основная операция в алгоритме будет сравнение так, как она выполняется на каждом шаге, а операция присваивание нет
3. В этом примере кол-во основных операций зависит только от размера массива

1. Размер n

2. Сравнение

3. В этой задаче у нас будет наилучший и наихудший случай. Рассмотрим наихудший случай, когда в массиве не будет одинаковых элементов или два одинаковых элемента будут в самом конце массива

4. У нас получится такая сумма

1. Размер n
2. Основная операция может быть сложение или умножение. Мы выберем умножение
3. Кол-во операций зависит от кол-ва вводимых элементов

1. Размер n
2. Основной операцией является сравнения n>1, но она не находится внутри цикла while. Однако выбор основной операции не имеет большого значения.
3. Кол-во операций зависит от n, которое каждый раз делится на 2, что делает алгоритм эффективным
4. Так как n всегда уменьшается в 2 раза, то результат должен быть примерно log2n.
5. На самом деле точная формула будет равна log2n+1(такой же ответ мы могли получить, применив методы, основанные на анализе рекуррентных соотношений в рекурсивных алгоритмах)