Блог

Главная - Вопросы по программированию - Мне нужна помощь в определении временной сложности этой функции

Мне нужна помощь в определении временной сложности этой функции

#time-complexity #big-o

#временная сложность #big-o

Вопрос:

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

 int exp2 (int a, int b)
{
        if (b==1)
        return a;
    Else
        return a*exp2(a,b-1);
}

Ответ №1:

O(b).

Обратите внимание, что функция будет повторяться b раз, выполняя одну операцию (умножение).

 (1) exp(4, 20) = 4 * exp(4, 19)
(2) exp(4, 19) = 4 * exp(4, 18) 
(3) exp(4, 18) = 4 * exp(4, 17)  
...
(b) exp(4, 1) = 4

Комментарии:

1. Итак, то, как я это видел, и, возможно, вы можете сказать мне, почему я ошибаюсь, заключается в том, что саму функцию нужно будет повторить b-1 раз на основе значения b, очевидно, но затем, как только это будет завершено, ей нужно рекурсивно умножить a на значение, возвращенное последующими функциями… я слишком много думаю об этом?

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

3. В этом случае операция, которую вы выполняете, является * . Сколько * вы сделаете за exp(4, 20) ? Как я показал в примере, это будут b - 1 операции * , следовательно, сложность равна O(b - 1) = O(b) .

4. Большое спасибо за ответ и объяснение!

Ответ №2:

Это эквивалентно возведению a в степень b-1 . Количество используемых операций равно b-1 . Она увеличивается пропорционально b такой сложности O(b) .