Точный метод для определения временной сложности функции - PullRequest
Новая
       78

Точный метод для определения временной сложности функции

0 голосов
/ 03 марта 2019

Как найти временную сложность этой функции:

Код 

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("~");
}

Я сделал обоснованное предположение (n^2)*log(n) на основе интуиции, и оказалось, чточтобы быть правильным.

Но я не могу найти точное объяснение этому.

1 Ответ

0 голосов
/ 03 марта 2019

Для каждого значения i, i>0 будут i-1 значения внутреннего цикла, каждое из которых для k начинается соответственно с: 

i*1, i*2, ..., i(i-1)

С k делится на 2 до достижения 0, для каждого из этих внутренних-внутренних циклов требуется lg(k) шагов.Следовательно, 

lg(i*1) + lg(i*2) + ... + lg(i(i-1)) = lg(i) + lg(i) + lg(2) + ... + lg(i) + lg(i-1)
                                     = (i-1)lg(i) + lg(2) + ... + lg(i-1)

Следовательно, итоговая сумма будет 

f(n) ::= sum_{i=1}^{n-1} i*lg(i) + lg(2) + ... + lg(i-1)

Давайте теперь свяжем f(n+1) сверху: 

f(n+1) <= sum_{i-1}^n i*lg(i) + (i-1)lg(i-1)
       <= 2*sum_{i-1}^n i*lg(i)
       <= C*integral_0^n x(ln x)            ; integral bound, some constant C
        = C/2(n^2(ln n) - n^2/2)            ; integral x*ln(x) = x^2/2*ln(x) - x^2/4
        = O(n^2*lg(n))

Если мы теперь привязаем f(n+1) отниже: 

f(n+1) >= sum_{i=1}^n i*lg(i)
       >= C*integral_0^n x(ln x)            ; integral bound
        = C*(n^2*ln(n)/2 - n^2/4)           ; integral x*ln(x) = x^2/2*ln(x) - x^2/4
       >= C/4(n^2*ln(n))
        = O(n^2*lg(n))
...