Большой (O) рекурсивный n выбирает k код

Question

Является ли большой (O) следующий рекурсивный код просто O (n выбирает k)?

int nchoosek(int n, int k) { 
    if (n == k) return 1; 
    if (k == 0) return 1; 
    return nchoosek(n-1, k) + nchoosek(n-1, k-1); 
} 

Answer 1

Я не уверен, если запись является правильным, но я думаю, вы можете написать повторения для этой функции, как

T(n) = T(n-1, k) + T(n-1, k-1) + O(1) 

Поскольку у вас есть два возможных пути мы просто должны проанализировать худший случай каждого и выбрать самый медленный.

Худший случай T(n-1, k)

Учитывая, что 0<k<n и k находится как можно дальше от n то мы имеем

T(n-1, k) = T(n-1) = O(n) 

Худший случай T(n-1, k-1)

Нам нужно 0<k<n и k shoul d как можно ближе к n. Тогда

T(n-1, k-1) = T(n-1) = O(n) 

Поэтому T(n, k) = 2*O(n) + O(1) = O(n)

Другой способ увидеть это за счет уменьшения проблемы с другими известными проблемами, например, вы можете решить ту же проблему, используя определение функции выбора в терминах Факториал функция:

nCk = n!/k!(n-k)! 

Хронометраж факторного является O(n) даже в рекурсивном случае.

nCk требует вычисление факториала три раза:

n! => O(n) 
k! => O(k) = O(n) 
(n-k)! => O(n-k) = O(n) 

Тогда умножение и деление как постоянное время O(1), следовательно, время работы является:

T(n) = 3*O(n) + 2*O(1) = O(n)