Анализ временной сложности кода

воспринимайте это как рекурсивную функцию:

f(i) = f(i-1)^3

если вы расширяете ее:

f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)

функция растет по мере увеличения мощности ... поэтому время (итераций) для достижения определенное число (то есть вычисление обратной функции) является логарифмом логарифма.

Как и в вашем примере f (0) = 2 , мы хотим знать, когда f ( i)> = n , являющееся n входным параметром (и i количество итераций):

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(n))

Таким образом, чтобы достичь значения n , он принимает log_3 (log_2 (n)) итераций (округление в большую сторону при работе с целыми числами, чтобы превзойти его).

если бы функция была:

f(i) = 2*f(i-1) //e.g. x=2*x

, то шаблон был бы:

f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)

И в этом случае функция, обратная функции, будет логарифмом по основанию 2.

Мои вычисления не очень строгие, но я надеюсь, что вы »Я уловлю идею.

Если бы код внутри цикла while был

x = 2*x;

, x достиг бы n за O (log (n)) итераций. Поскольку вы занимаетесь кубом x, а не просто умножаете его на константу, вы достигнете n быстрее.

Учитывая

log ( A * x )     == log ( A ) + log ( x )
log ( x * x * x ) == 3 * log ( x )

Итак

log ( log ( x * x * x ) ) == log ( 3 * log ( x ) )
                          == log ( 3 ) + log ( log ( x ) )

Насколько быстрее или медленнее (измеряется количеством итераций цикла) будет ли эта функция отличаться от вашей?

int log_foo ( int n ) 
{
    double          log_x = log ( 2 );
    const double    log_n = log ( n );

    while ( log_x < log_n )
    {
        log_x = 3 * log_x;
    }

    return exp ( log_x );
}

И насколько эта функция будет быстрее или медленнее, чем ваша функция?

int log_log_foo ( int n ) 
{
    double          log_log_x = log ( log ( 2 ) );
    const double    log_log_n = log ( log ( n ) );
    const double    log_3     = log ( 3 );

    while ( log_log_x < log_log_n )
    {
        log_log_x += log_3;
    }

    return exp ( exp ( log_log_x ) );
}

Но эта функция увеличивает log_log_x только на константу, поэтому ее легко вычислить сколько итераций он делает.

Подумайте о том, как x изменяется с числом итераций в цикле. Каждый раз вы собираете его в куб. Итак, после i итераций значение будет 2 раза в кубе, снова в кубе ... и так далее, i раз. Давайте использовать x (i) для обозначения этого выражения. Скажем, x (0) = 2, x (1) = 2 3 и т. Д. (Я использую b для обозначения возведения в b-ю степень).

Мы закончили, когда x (я)> = п. Сколько времени это занимает? Давайте решим для i.

First, we take a log on both sides: ln(x(i))>=ln(n)

ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i)

(the above uses [this property][1]: ln(x**b)==ln(x)*b)

so, 3**i * 2 >=ln(n). Let's take another logarithm:

ln(3**i * 2) = ln(2) + ln(3)*i 

so ln(2) + ln(3)* i >= ln(ln(n))

Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)

Мы можем игнорировать постоянные множители, и нам остается сделать вывод, что мы предпримем log (log (n)) шагов. В этом сложность вашего алгоритма.

Надеюсь, что подобная разбивка всех шагов поможет.

Пусть i будет числом шагов итерации, а x (i) значение x после i шагов. У нас есть

x(0) = 2
x(i) = x(i-1)³

Общее количество шагов является наибольшим i , так что x (i) .

log x(i) = log x(i-1)³
         = 3·log x(i-1)
         = 3·log x(i-2)³
         = 3²·log x(i-2)
         = 3^i·log x(0)
         = 3^i·log 2

⇒  log log x(i) = log (3^i·log 2)
                 = log 3^i + log log 2
                 = i·log 3 + log log 2

x(i) < n ⇔        log log x(i) < log log n
         ⇔ i·log 3 + log log 2 < log log n
         ⇔                   i < (log log n - log log 2) / log 3 ∈ O(log log n)