Решение задачи: Оценка трудоемкости рекурсивной функции

Для определения верхней точной асимптотической оценки трудоемкости функции \(f(n)\), проанализируем структуру рекурсивных вызовов. 1. Анализ кода: Внутри функции \(f(n)\) происходят следующие вызовы: — Один вызов \(f(n-1)\). — Цикл `for (int j = 0; j < 12; j++)`, внутри которого вызывается \(f(n-2)\). Это означает, что \(f(n-2)\) вызывается ровно 12 раз. 2. Составление рекуррентного соотношения: Пусть \(T(n)\) — количество вызовов (трудоемкость) для аргумента \(n\). Тогда: \[ T(n) = T(n-1) + 12 \cdot T(n-2) + C \] где \(C\) — константа, описывающая элементарные операции внутри функции. 3. Решение характеристического уравнения: Для нахождения асимптотики вида \(a^n\) составим характеристическое уравнение: \[ r^2 - r - 12 = 0 \] Найдем корни через дискриминант: \[ D = (-1)^2 - 4 \cdot 1 \cdot (-12) = 1 + 48 = 49 \] \[ r_1 = \frac{1 + 7}{2} = 4 \] \[ r_2 = \frac{1 - 7}{2} = -3 \] 4. Определение асимптотики: Общее решение рекуррентного соотношения имеет вид: \[ T(n) = C_1 \cdot 4^n + C_2 \cdot (-3)^n \] Наибольший по модулю корень определяет скорость роста функции. В данном случае это \(4\). Следовательно, трудоемкость растет как экспоненциальная функция: \[ T(n) = O(4^n) \] Ответ: b. O(4^n)