Почему код типа i=i*2 считается O(logN) в цикле?

Почему из-за i=i*2 время выполнения цикла ниже считается O(logN)?

for (int i = 1; i <= N;) {
  code with O(1);
  i = i * 2;
}

time-complexity big-o logarithm
person George    schedule 12.03.2017    source источник
comment
Вы уверены, что имеете в виду строку, содержащую умножение? Общий цикл имеет логарифмическую сложность.   -  person C-Otto    schedule 13.03.2017
comment
Я имею в виду, общий цикл, все еще новый для этого.   -  person George    schedule 13.03.2017

Ответы (4)


arrow_upward
3
arrow_downward

Посмотрите на 1024 = 210. Сколько раз нужно удвоить число 1, чтобы получить 1024?

Times    1   2   3   4    5    6    7    8     9      10
Result   2   4   8   16   32   64  128  256   512    1024

Таким образом, вам придется запустить цикл удвоения десять раз, чтобы получить 210. И вообще, вам нужно запустить цикл удвоения n раз, чтобы получить 2n. Но что такое н? Это log2 2n, поэтому, как правило, если n равно степени 2, цикл должен выполниться log2n раз, чтобы достичь Это.

person Tashi    schedule 12.03.2017

arrow_upward
2
arrow_downward

Чтобы иметь алгоритм в O(logN), для любого N ему потребуется (около) log N шагов. В примере с N=32 (где log 32 = 5) это видно:

i = 1 (start)
i = 2
i = 4
i = 8
i = 16
i = 32 (5 iterations)
i = 64 (abort after 6 iterations)

Как правило, после x итераций выполняется i=2^x. Чтобы добраться до i>N, вам нужно x = log N + 1.

PS: Когда речь идет о сложностях, основание log (2, 10, e, ...) не имеет значения. Кроме того, не имеет значения, есть ли у вас i <= N или i < N, так как это только меняет количество итераций на единицу.

person C-Otto    schedule 12.03.2017

arrow_upward
1
arrow_downward

Доказать это можно довольно просто.

Утверждение: Для tй (0 базы) итерации, i=2^t Доказательство по индукции.

База: 2^0 = 1, и действительно в первой итерации i=1.

Шаг: Для некоторого t+1 значение i равно 2*i(t) (где i(t) — это значение i в t итерации). Из гипотезы индукции мы знаем, что i(t)=2^t и, следовательно, i(t+1) = 2*i(t) = 2*2^t = 2^(t+1), и утверждение верно.

Теперь давайте рассмотрим наши критерии остановки. Мы повторяем цикл, пока i <= N, и из приведенного выше утверждения это означает, что мы повторяем, пока 2^t <= N. Выполняя log_2 с обеих сторон, мы получаем log_2(2^t) <= log_2(N), а начиная с log_2(2^t) = t, мы получаем, что мы итерируем while t <= log_2(N), то есть мы итерируем Theta(log_2(N)) раз. (И это завершает доказательство).

person amit    schedule 12.03.2017

arrow_upward
0
arrow_downward

i начинается с 1, затем в каждой итерации вы умножаете его на 2, что означает:

в некотором K 2^(K-1) будет больше (или равно), чем N.

это означает N ‹= 2^(K-1)

это означает log(N) ‹= K-1

K-1 будет числом итераций, которые будет выполнять ваш цикл, а поскольку K-1 больше или равно log(N), ваш алгоритм логарифмический.

person Daniel    schedule 12.03.2017