Анализ временной сложности кода
-
07-07-2019 - |
Вопрос
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))
.Итак, как вы подходите к такому вопросу?
Решение
Пусть
L3 = вход на базу 3 L2 = Вход на базу 2
Тогда правильный ответ таков O(L3(L2(n)) а НЕ O(L2(L2(n)).
Начните с x = x * 2.x будет увеличиваться экспоненциально, пока не достигнет n, тем самым увеличивая временную сложность O (L2 (n))
Теперь рассмотрим x = x * 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.Это будет увеличиваться даже быстрее, чем 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(логарифмическая привязкак базе-3(логарифмическая привязкакбазе-2(n))
Обобщая это, если x = x * x * x * x * ..(k раз), тогда временная сложность равна O(логарифмическая связь с базой-k(логарифмическаясвязьс базой-2(n)
Другие советы
думайте об этом как о рекурсивной функции:
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))
Таким образом, чтобы достичь значения 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.
Моя математика не очень строгая, но я надеюсь, что вы поймете идею.
Подумайте, как 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)) шаги. Это сложность вашего алгоритма.
Надеюсь, если разбить все шаги, как это помогает.
Если код внутри цикла 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
с помощью константы, так что легко подсчитать, сколько итераций она выполняет.
Пусть i
будет числом шагов итерации и x(i)
значением x
после x(i) < n
шагов. У нас есть
x(0) = 2
x(i) = x(i-1)³
Общее количество шагов самое большое <=>, поэтому <=>.
У нас есть
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)
Почему бы не добавить переменную-счетчик для подсчета количества итераций цикла. Распечатайте его непосредственно перед возвратом функции.
Затем вызовите функцию для диапазона значений, например, От 3 до 1 000 000 для начала. Затем нарисуйте свой результат, используя что-то вроде GNUPlot . Р>
Затем посмотрите, соответствует ли график известной кривой.