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

Question

int foo(int n) 
{
    int x=2;
    while (x<n)
    {
        x = x*x*x;
    }

    return x;
}

Мне нужно проанализировать его временную сложность. Я заметил, что он достигает n намного быстрее, чем просто log(n). Я имею в виду, он делает меньше шагов, чем сделал бы O(log(n)). Я прочитал ответ, но понятия не имею, как они к нему пришли: это O(log(log(n)). Теперь, как вы подходите к такому вопросу?

Answer 1

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

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, оно takes 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.

Моя математика не очень строгая, но я надеюсь, что вы поймете эту идею.

Answer 2

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

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

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)) шаги. Это сложность вашего алгоритма.

Надеюсь, если разбить все шаги, как это помогает.

Answer 3

Пусть

L3 = войти в базу 3 L2 = Вход в базу 2

Тогда правильный ответ будет O (L3 (L2 (n)) и НЕ O (L2 (L2 (n))).

Начните с x = x * 2 . x будет экспоненциально увеличиваться, пока не достигнет n, что сделает сложность по времени O (L2 (n))

Теперь рассмотрим x = x * x . х увеличивается быстрее, чем выше. На каждой итерации значение x переходит на квадрат своего предыдущего значения. Делая простую математику, вот что мы получаем:

для х = 2 n = 4, итераций принято = 1 n = 16, выполнено итераций = 2 n = 256, выполнено итераций = 3 n = 65536, принятых итераций = 4

Таким образом, сложность времени составляет O (L2 (L2 (n)) . Вы можете убедиться в этом, поместив значения выше значений для n.

Теперь перейдем к вашей проблеме, x = x * x * x . Это будет увеличиваться даже быстрее, чем х = х * х. Вот таблица:

для х = 2 n = 8, выполнено итераций = 1 n = 512, итераций принято = 2 n = (512 * 512 * 512), выполненных итераций = 3 и т. д.

Если вы посмотрите на это внимательно, это окажется O (L3 (L2 (n)) . L2 (n) даст вам силу двух, но так как вы принимаете куб x в каждой итерации, вам нужно будет вести журнал к основанию 3, чтобы узнать правильное количество выполненных итераций.

Поэтому я думаю, что правильный ответ - O (log-to-base-3 (log-to-base-2 (n)) *

Обобщая это, если x = x * x * x * x * .. (k раз) , то сложность времени составляет O (log-to-base-k (log- к основанию-2 (п)

Answer 4

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

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

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

У нас есть

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)

Answer 5

Дано

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

So

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 на постоянную, поэтому легко определить, сколько итераций она выполняет.

Answer 6

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

x = 2*x;

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

Answer 7

Почему бы не добавить переменную-счетчик для подсчета количества итераций цикла. Распечатайте его непосредственно перед возвратом функции.

Затем вызовите функцию для диапазона значений, например, От 3 до 1 000 000 для начала. Затем постройте свой результат, используя что-то вроде GNUPlot .

Затем посмотрите, соответствует ли график известной кривой.