Решите повторение

12

Как я могу решить следующую рекуррентную связь?

f(n)=f(n1)+f(nlogn)
пельмени мобиус
источник
5
Что вы получите, если вы попытаетесь ? Похоже, что вы получите нижнюю границу 2 Ω ( n / log n ) . f(n)=2f(nlogn)2Ω(n/logn)
Чандра Чекури
2
@ChandraChekuri О, это здорово! И есть верхняя граница : мы используем журнал повторений n раз и получаем, что f ( n ) ( 1 + log n ) f ( n - log n ) . Затем мы применяем это n / log n раз и получаем f ( n ) ( 1 + log n2O(nloglogn/logn)lognf(n)(1+logn)f(nlogn)n/logn . Таким образом, разрыв между верхней и нижней границами составляет только log log n в показателе степени. На самом деле этого достаточно для моих целей, но я оставлю вопрос открытым, если кто-то захочет и сможет сократить разрыв. Большое спасибо, Чандра! f(n)(1+logn)n/logn=2O(nloglogn/logn)loglogn
клецки мобиуса
4
Ну, тот же трюк дает , поэтому f ( n ) = 2 Θ ( n log log n / log n ) . f(n)(logn)f(n2logn)f(n)=2Θ(nloglogn/logn)
Эмиль Йержабек

Ответы:

14

f(n)=2Θ(nloglogn/logn) .

logn

f(n)=2f(nlogn)+f(nlogn1)++f(n2logn)lognf(nlogn) .
n/logn2Ω(nloglogn/logn)

logn

f(n)(logn+1)f(nlogn) .
n/logn2O(nloglogn/logn)
пельмени мобиус
источник