Что вы получите, если вы попытаетесь ? Похоже, что вы получите нижнюю границу 2 Ω ( n / log n ) . f(n)=2f(n−logn)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(n−logn)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(n−2logn)f(n)=2Θ(nloglogn/logn)
Ответы:
источник