T (n) время выполнения для функции двух входов
Как бы вы нашли время выполнения T (n) (не время выполнения больших O) для функции, которая имеет два входа? Вы просто рассматриваете вход как ‘n’?
int h(int a, int b) {
if (a > 0) {
return h(a-1, a+b);
}
else {
return 0;
}
}
Решение
В этом случае нам просто нужно рассмотреть a поскольку длина этого алгоритма не зависит от б.
Другими словами, так как мы можем передать 20000 или -2 для b и не влиять на наше время ни в малейшей степени (игнорируя фактическое время добавления a+b) мы не должны учитывать b в наших расчетах.
В более общем случае, если входные данные зависят от a а также b мы бы просто учли это в нашей функции сложности времени. Другими словами это было бы T(a, b) не просто T(a),
Другие решения
так как эта функция повторяется только на a и a уменьшается на 1 на каждом шаге, это дало бы линейную сложность. Таким образом, ответ будет T (а).
Учитывая, что для каждой пары (a, b) значение функции равно нулю — рекурсия всегда заканчивается в ветви else — компилятор может быть достаточно умен, чтобы эффективно сократить код до «возврата 0» для всего тела и пропустить все if / else и рекурсию, что приведет к сложности O (1) и соответствующему времени выполнения.