Простая пока цикл Big-O сложность

Question

int a = 3;

while (a <= n) {
    a = a * a;
}

Моя версия такова:
http://www.mmoprophet.com/stuff/big-o.jpg
Есть ли такая вещь?

Answer 1

Это не правильно. a не может быть частью формулы big-O, поскольку это просто временная переменная.

Вне головы, если мы возьмем умножение как операцию с постоянным временем, то число выполненных умножений будет O (журнал журнала n ) . Если бы вы умножали на константу каждую итерацию, то это было бы O (log n ). Поскольку вы умножаете на растущее число каждую итерацию, то есть еще один журнал.

Думайте об этом как о количестве цифр, удваивающем каждую итерацию. Сколько раз вы можете удвоить количество цифр, прежде чем превысите лимит? Число цифр равно log n , и вы можете удвоить число начальных цифр log ₂ log n раз.

---

Что касается другого аспекта вопроса, то да, O ( a -й корень n ) может быть допустимым классом сложности для некоторой константы a . Это было бы более привычно записано как O ( n ^{1 / a} ) .

Answer 2

Ну, вы могли бы фактически пойти в бесконечный цикл!

Предположим, 32-разрядные целые числа:

Попробуйте это:

int a = 3 ;
int n = 2099150850;
while (a <= n)
{
    a = a*a;
}

Но если предположить, что нет целочисленных переполнений, другие постеры верны, это O (log logn), если вы предполагаете O (1) умножение.

Простой способ убедиться в этом:

x _{n + 1} = x _n ² .

Взять х ₁ = а.

Принимая журналы.

t _n = log x _n

Тогда t _{n + 1} = 2t _n

Я оставлю вам остальное.

Становится интереснее, если учесть сложность умножения двух цифр на номера k.

Answer 3

После i-й итерации (i = 0,1, ...) значение a равно 3 ^{2 i} . Будет O (log log n) итераций, и при условии арифметических операций в O (1) это сложность времени.

Answer 4

Количество итераций цикла равно & Omicron; (log log n). Само тело цикла выполняет присваивание (которое мы можем считать постоянным) и умножение. На сегодняшний день самый известный алгоритм умножения имеет ступенчатую сложность & Omicron; (n & thinsp; log & thinsp; n & times; 2 ^{& Omicron; (log * & thinsp; n)} ), поэтому все вместе сложность что-то вроде:

& Омикрон; (войти войти п & thinsp; & времена; & thinsp; п & thinsp; войти & thinsp; п & раз; 2 ^{& Омикрон; (журнал ** +1010 * & thinsp; п) )}

В более читабельном виде:

Ο (log log n × n log n × 2 ^ Ο (log * n)) http://TeXHub.Com/b/TyhcbG9nXGxvZyBuXCxcdGltZXNcLG4gXGxvZyBuXCxcdGltZXNcLDJee08oXGxvZ14qIG4pfSk=