Почему counter = counter / 2; есть O (log (n))?

Question

Я знаю, что следующий код имеет сложность O (log (n)):

while (n>1)
{
    counter++;
    n/=2;
}

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

Извините за простой вопрос, я действительно старался изо всех сил, чтобы получить его, прежде чем я спросил.

Answer 1

Каждый раз, проходя через цикл, вы делите на 2 (примерно; при этом округление игнорируется, поскольку это асимптотический аргумент). Так что, если n = N в начале, после k итераций, n = N / (2 ^ k). Чтобы получить n = 1, вы должны удовлетворить 2 ^ k = N. То есть k = log (N).

Answer 2

Отношение повторения будет

 T(n) = T(n/2) + O(1)

Попытка решить ее с помощью Теорема мастера даст время выполнения T (n) как O (log n) (аналогично тому, что вы получаете в бинарном поиске).

Answer 3

Простое волнообразное объяснение: что произойдет, если вы удвоите n?Удваивается ли время выполнения (это будет O (n))?Нет, время выполнения увеличивается на только на один шаг .Это типично для O (log n).

[OTOH, если вы возвели в квадрат n (скажем, оно увеличилось с 4 до 16), то вы обнаружите, что количество шагов удваивается.Опять же, указывает на O (log n).]

Answer 4

По определению, логарифмы не являются линейными. Другими словами, они меняются на разные величины в зависимости от ввода. В вашем примере первый шаг уменьшает n на 500, а пятый - только на 32. Чем ближе вы к нему, тем медленнее n уменьшается. Это «замедление» - именно то поведение, которое вы получаете с журналом.

Answer 5

Представьте, что n равно 2 ^ x (например, 2 ^ 5 = 32, 2 ^ 10 = 1024 и т. Д.), Так что счетчик увеличивается в x раз в цикле.По определению, x является основанием 2 log n.