Большая сложность кода кода

У меня вопрос в дизайне алгоритма о сложности. В этом вопросе предоставляется кусок кода, и я должен рассчитать эту сложность кода. Псевдокод:

for(i=1;i<=n;i++){
    j=i
    do{
        k=j;
        j = j / 2;
    }while(k is even);
}

Я попробовал этот алгоритм для некоторых чисел. и я получил разные результаты. например, если n = 6, этот выход алгоритма выглядит как ниже

i = 1 -> executes 1 time
i = 2 -> executes 2 times
i = 3 -> executes 1 time
i = 4 -> executes 3 times
i = 5 -> executes 1 time
i = 6 -> executes 2 times

У него нет обычной темы, как мне рассчитать это?

Ответ 1

Верхняя граница, заданная другими ответами, на самом деле слишком высока. Этот алгоритм имеет время выполнения O (n), которое является более жесткой верхней границей, чем O (n * logn).

Доказательство. Пусть подсчет количества полных итераций, которые будет выполнять внутренний цикл.

Внешний цикл работает n раз. Внутренний цикл выполняется по крайней мере один раз для каждого из них.

Для четного i внутренний цикл выполняется не менее двух раз. Это происходит n/2 раза.
Для i, делящегося на 4, внутренний цикл выполняется как минимум три раза. Это происходит n/4 раз.
Для i, делящегося на 8, внутренний цикл выполняется не менее четырех раз. Это происходит n/8 раз.
...

Таким образом, общее количество раз, когда выполняется внутренний цикл:

n + n/2 + n/4 + n/8 + n/16 + ... <= 2n

Общее количество итераций внутреннего цикла находится между n и 2n, то есть Θ (n).

Ответ 2

Вы всегда предполагаете, что вы получаете худший сценарий на каждом уровне.
теперь вы перебираете массив с N элементами, поэтому мы начинаем с O(N) уже.
теперь пусть ваш i всегда равен X, а X всегда равен (помните, худший случай каждый раз).
сколько раз вам нужно разделить X на 2, чтобы получить 1? (это единственное условие для четных чисел, чтобы остановить деление, когда они достигают 1).
другими словами, нам нужно решить уравнение X/2^k = 1, который равен X=2^k и k=log<2>(X) это заставляет наш алгоритм принимать шаги O(n log<2>(X)), которые можно легко записать как O(nlog(n))

Ответ 3

Для такого цикла мы не можем разделить счетчик внутреннего цикла и внешнего цикла → переменные затянуты!

Таким образом, мы должны считать все шаги.

Действительно, для каждой итерации внешнего цикла (на i) мы будем иметь

1 + v_2(i) steps

где v_2 - 2-адическое нормирование (см. например: http://planetmath.org/padicvaluation), который соответствует мощности 2 в разложении в простой коэффициент i.

Итак, если мы добавим шаги для всех i, мы получим общее количество шагов:

n_steps = \sum_{i=1}^{n} (1 + v_2(i)) 
        = n + v_2(n!)    // since v_2(i) + v_2(j) = v_2(i*j)
        = 2n - s_2(n)    // from Legendre formula (see http://en.wikipedia.org/wiki/Legendre%27s_formula with `p = 2`)

Затем мы видим, что количество шагов точно:

n_steps = 2n - s_2(n)

Поскольку s_2(n) представляет собой сумму цифр n в базе 2, она пренебрежимо мала (не более log_2(n), так как цифра в базе 2 равна 0 или 1 и, поскольку существует не более log_2(n)) по сравнению с n.

Таким образом, сложность вашего алгоритма эквивалентна n:

n_steps = O(n)

который не O(nlog(n)), указанный во многих других решениях, но меньшая величина!

Ответ 4

позволяет начать с наихудшего случая:

если вы продолжаете делиться с 2 (интегральными), вам не нужно останавливаться, пока вы перейти к 1. в основном, делая количество шагов, зависящих от ширины бита, то, что вы узнаете, используя два логарифма. поэтому внутренняя часть - log n. внешняя часть, очевидно, равна n, поэтому N log N total.

Ответ 5

A do половины цикла j, пока k не станет нечетным. k изначально является копией j, которая является копией i, поэтому do запускает 1 + мощность 2, которая делит i:

я = 1 нечетно, поэтому он проходит 1 проход через цикл do,
я = 2 делится на 2 один раз, поэтому 1 + 1,
я = 4 делится дважды на 2, поэтому 1 + 2 и т.д.

Это делает не более 1 + log (i) do исполнений (логарифм с базой 2).

Цикл for выполняет итерацию i от 1 до n, поэтому верхняя граница n times (1 + log n), которая равна O (n log n).