Расчет сложности этой функции

Question

Это функция:

void f(int n)
{
 for(int i=0; i<n; ++i)
   for(int j=0; j<i; ++j)
     for(int k=i*j; k>0; k/=2)
       printf("~");
}

На мой взгляд, вычисление сложности времени в конечном итоге будет примерно таким:

log((n-1)(n-2))+log((n-1)(n-3))+...+log(n-1)+log((n-2)(n-3))+...+log(n-2)+...log(2)

Итак, я получаювременная сложность nlog(n!) (потому что loga+logb=log(a*b) и потому что n-1, n-2, n-3, ... каждый появляется в общей сложности n-1 раз.

Однако, правильный ответ n^2*logn, и я понятия не имею, где моя ошибка. Может ли кто-нибудь здесь помочь?

Большое спасибо!

Answer 1

log(n!) можно аппроксимировать как (n+1/2)log(n) - n + constant (см. https://math.stackexchange.com/questions/138194/approximating-log-of-factorial)

Таким образом, сложность равна n*n*log(n), как и ожидалось.

Проще: вычислять цикл сложности за циклом независимо иумножьте их.

Первые 2 внешних цикла: тривиальные: n каждый, что составляет n^2

Внутренний цикл: имеет log(n**2) сложность, которая равна log(n)

Итак, n^2log(n) - правильный ответ.

Answer 2

Сложность равна O(N*N*LOG_2(N^2)).

Первый и второй циклы имеют O(N), а последний цикл в k имеет логарифмический рост.

LOG_2(N^2) = 2*LOG_2(N) and
O(N*M)=O(N)*O(M).
O(constant)=1.

Так что длярост последнего цикла вы можете написать также O(LOG_2(N^2))=O(LOG(N)).