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

План анализа эффективности рекурсивных алгоритмов

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

1. Размер входных данных n

2. Основной операцией является умножение

3. Кол-во выполнений будет M(n)