Сложность базового алгоритма?

Question

У меня есть этот пример алгоритм:

int sum = 0; 
int j = 1; 
while (j <= n) { 
    sum++; 
    j = j * 2; 
} 

Книга, которую я читаю, «Строительные Программы Java - это Назад к подходу Основы» говорят мне, что мне нужно, чтобы найти это:

Приблизительного время выполнения следующий фрагмент кода в терминах n: Напишите свой ответ в формате, таком как O(N^2) или O(N log N).

Кажется, я не понимаю, как добраться от пункта a до пункта b здесь. Я вычислил два утверждения = O(2) и цикл с двумя операторами = O(2N), поэтому он должен быть O(2N + 2). Где я иду не так?

Answer 1

При определении сложностей мы не включаем константы или коэффициенты. Вместо O (2N + 2) это должно быть O (n). Мы только заботимся о числах, если они экспоненциальны, т. Е. 2 ​​^ n или n^2, log2 (n) и т. Д.

Отложив это в сторону, вы уверены, что это O (n)? O (n) означает, что он работает n раз, но похоже, что j собирается догнать n до n раз. Видите, что я говорю?

EDIT: Хорошо, вот что происходит.

Посмотрите, что происходит с j. j = j * 2. j удваивается каждый раз. Другими словами, разница между j и n составляет пополам. Когда количество оставшихся итераций сокращается наполовину на каждой итерации, это называется алгоритмом log (n). log (n) алгоритмы довольно удивительны, потому что даже если n чрезвычайно велико, log (n) на удивление мало. Подключите некоторые цифры, чтобы понять, что я имею в виду.

Answer 2

Петля не перебирает каждое значение от 1 до N, где находится ваш O (2N).

Это может помочь визуализировать выполнения, если заменить программу со следующим, который будет иметь ту же сложность - это похоже на алгоритмы, которые вдвое сократить размер входного сигнала на каждой итерации

int j = n; 
while(j > 1) { 
    j = j/2; 
} 

Answer 3

Для того, чтобы определить сложность, вы на правильном пути, пытаясь найти количество операций! То, что я обычно делаю, если не могу сразу вытащить формулу: сначала я нахожу примеры. Попробуйте это для n = 5, n = 8, n = 64, n = 65 и придумайте количество выполненных шагов, и вы скоро увидите шаблон!

Формула для числа операций, которые вы придумали, может быть очень точной, но вы можете оставить константы для определения порядка сложности (множители и дополнительные константы), так как в конце O (2n) есть примерно такой же, как O (3n) по сравнению с O (n^2).

Answer 4

Ваш вопрос задает вопрос приблизительно время, точное время или формула не требуется.

Кроме того, Big O Notation, например. O (N), имеет тенденцию быть , упрощен до самого доминирующего термина только (т. Е. Член N, где, если N очень велико, этот термин предоставит точный или почти точный ответ).

Итак, если ваша точная формула была, скажем, 4N^2 + 9N + 7, ваш ответ будет O (N^2). Поскольку, если N было очень большим, одного члена N^2 было бы достаточно, чтобы приблизить ответ.

Кроме того, YTS имеет точку относительно переменной J, как это экспоненциально меняется, поэтому от вашего кода время, т будет:

т = 2 (сумма) + 2 = 2 (log2 (п) +1) + 2

Поэтому ваше решение может быть, в виде O (N журнал), или, возможно, O (log2 N)?

Answer 5

Я бы сказал, сломайте его; такая проблема выглядит обманчиво простой сразу, но доказательство ее было бы ценным.

Предположим, п = 100.

• Первая итерация: sum = 1, j = 2
• Вторая итерация: sum = 2, j = 4
• Третья итерация: sum = 3, j = 8
• Четвертая итерация: sum = 4, j = 16
• Пятая итерация: sum = 5, j = 32
• Шестая итерация : sum = 6, j = 64
• Седьмая итерация: sum = 7, j = 128 # конец итераций.

Если это произошло во время O (N), тогда вы ожидаете около ста итераций. Вместо этого мы вместо этого увеличиваем j в 2 раза, достигая терминальной итерации примерно семь раз.

При этом мы итерации по крайней мере один раз (для n> 1), плюс пол log(100)/log(2) = 6, в общей сложности 7 раз.

Я склонен полагать, что, основываясь на выполнении этого небольшого теста, время выполнения этого: O (log (n)), а не O (n).

Напомним, от this graph; логарифмы растут гораздо медленнее с течением времени при больших значениях N. Даже при n = 1000 вы увидите только 10 итераций.