Блог

Главная - Вопросы по программированию - Точный метод определения временной сложности функции

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

#c #for-loop #time-complexity

#c #для цикла #временная сложность

Вопрос:

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

Код

 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. Похоже, единственная сложная часть — это то, как справиться с k=i*j . С этим можно справиться, осознав, что log(n^2) = 2log(n) а big-O игнорирует константы.

2. Действительно, это правда, я заметил эти вещи, но дело в том, что, как вы сказали, часть i j сбивает с толку. Самый внутренний цикл выполняется log (i j) раз, поэтому здесь у нас есть какая-то сумма, которую я, похоже, не могу точно сформулировать

3. А, я понимаю. Вы ищете точную формулу, например 1 2 3 ... n = n(n 1)/2 . Я не уверен, что для этого кода существует такая формула, но вы можете попытать счастья на math stack exchange .

Ответ №1:

Для каждого значения 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))