Простой цикл с условием продолжения Большая-O сложность
int a = 3; while (a <= n) { a = a * a; }Моя версия - то, что ее сложность:
http://www.mmoprophet.com/stuff/big-o.jpg
Есть что-то такое?
4 ответа
Это неправильно. a не может быть частью формулы большого О, поскольку это всего лишь временная переменная.
Я не понимаю, если мы возьмем умножение как операцию с постоянным временем, то количество выполненных умножений будет O (log log n ) . Если бы вы умножали на константу на каждой итерации, это было бы O (log n ). Поскольку вы умножаете на растущее число на каждой итерации, появляется еще один журнал.
Думайте об этом как о количестве цифр, удваиваемых на каждой итерации. Сколько раз вы сможете удвоить количество цифр, прежде чем превысите лимит? Количество цифр равно log n , и вы можете удвоить начальные цифры log 2 log n раз.
Что касается другого аспекта вопроса, да, O ( -й корень из n ) может быть допустимым классом сложности для некоторой константы a . Более привычно его можно было бы записать как O ( n 1 / a ) .
После i-й итерации (i=0,1,...) значение a равно 32i. Будет O(log log n) итераций, и если предположить, что арифметические операции в O(1), то это временная сложность.
Ну, вы действительно можете зайти в бесконечный цикл!
Предположим, 32-битные целые числа:
Попробуйте следующее:
int a = 3 ;
int n = 2099150850;
while (a <= n)
{
a = a*a;
}
Но если предположить, что нет целочисленных переполнений, другие плакаты верны, это O (log logn), если вы предполагаете умножение O (1).
Простой способ увидеть это:
x n + 1 = x n 2 .
Возьмем x 1 = a.
Взятие журналов.
t n = log x n
Тогда t n + 1 = 2t n
Остальное я оставлю вам.
Это станет более интересным, если учесть сложность умножения двух k-значных чисел.
Число итераций цикла равно Ο(log log log n). Само тело цикла выполняет присваивание (которое мы можем считать постоянным) и умножение. Самый известный на сегодняшний день алгоритм умножения имеет пошаговую сложность Ο(n log n×2Ο(log* n)), поэтому в целом сложность составляет примерно:
Ο(log log n × n log n×2Ο(log* n))
В более читаемой форме: