Что такое большой O этого небольшого фрагмента кода?

for i := 1 to n do 
    j := 2; 
    while j < i do 
    j := j^4;

Я действительно смущен, когда речь идет о нотации Big-O, поэтому я хотел бы знать, если это O (n log n). Это моя кишка, но я не могу это доказать. Я знаю, что цикл while, вероятно, быстрее, чем log n, но я не знаю, насколько!Что такое большой O этого небольшого фрагмента кода?

Редактировать: каретка обозначает экспоненту.

источник

2010-09-02 user438293456

Что делает 'j^4'? Является ли это XOR или возведение в степень? – MAK

После шагов 'k' внутреннего цикла' j' строго больше, чем '2^k'. Таким образом, существует не более стадий внутреннего цикла log log, и, конечно, «n» шагов внешнего цикла. Это ваше доказательство того, что op - O (n log n) - предполагая, конечно, что задействованные типы - это мифические «целые числа, которые никогда не переполняются, а имеют арифметические операции с постоянным временем» ;-). Для реалистичных диаграмм нужно учитывать некоторые дополнительные полиномиальные термины в 'log n', а для реалистичных int-int фиксированного размера' j' так быстро взрывается, что переполнение происходит для многих значений 'i' и' j' застрял на 0 ... –

Проблема заключается в количестве итераций, цикл while выполнен для заданного i.

На каждой итерации j:= j^4 и в начале j := 2, поэтому после x итераций j = 2^{4^x}

j < i эквивалентно x < log_4(log_2(i))

Я бы рисковать с заявлением, что сложность O(n * log_4(log_2(n)))

Вы можете избавиться от постоянных факторов в нотации Big O. log_4(x) = log(x)/log(4) и log(4) - постоянная. Аналогичным образом вы можете изменить log_2(x) на log(x). Сложность может быть выражена как O(n*log(log(n)))

источник

2010-09-02 22:07:31

+1 Я считаю, что это правильно. И так как примечание Big-O игнорирует умножение на константу M, это эквивалентно O (n log (log (n)). Таким образом, OP прав, цикл while быстрее, чем log (n). – LarsH

экспромтом, я предположил бы, что это представляет собой О (п утомительной п), где slog представляет собой инверсию tetration operator. Тетрация - следующая операция после возведения в степень. Точно так же, как умножение - это повторное добавление, а возведение в степень - повторное умножение, тетация - это итерационное возведение в степень.

Мои рассуждения, если умножить J на 4 каждой итерации, то функция будет O ( п журнал п). Но так как вы оцениваете его каждую итерацию, вам нужен более мощный оператор, чем журнал: slog.

источник

2010-09-02 22:03:42

+1 Я не уверен, что вы правы, но это находчивые рассуждения. :-) – LarsH

Хм, да, думая об этом, все это кажется неправильным. Но я оставлю ответ за образовательную ценность! Хех. –

lol, я думал, что это (по существу) этот оператор тоже! Это не ответ, но теперь я знаю, что это называется! (Googling «log log log» не приносил мне удачи. Haha – user438293456

Что такое большой O этого небольшого фрагмента кода?

ответ

Смежные вопросы