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

Question

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

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

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

он не имеет регулярной темы, как я должен вычислить это?

625 5

algorithm time-complexity

5 ответов:

Comments

Ничего не найдено.

interjay · Accepted Answer · 2015-05-15 01:14:15

верхняя граница, заданная другими ответами, на самом деле слишком высока. Этот алгоритм имеет время выполнения 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).

David Haim · Accepted Answer · 2015-05-14 12:15:35

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

Samuel Caillerie · Accepted Answer · 2015-06-17 17:12:35

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

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

фактически, для каждой итерации внешнего цикла (on 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)
что это не the O(nlog(n)) заявлено во многих других решениях, но в меньшем количестве!

sp2danny · Accepted Answer · 2015-05-14 12:12:09

давайте начнем с худшего случая:

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

CiaPan · Accepted Answer · 2015-05-14 12:17:37

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

i=1 нечетно, поэтому он делает 1 проход через do цикл

i=2 делится на 2 один раз, так что 1+1,

i=4 делит дважды на 2, поэтому 1+2 и т. д.

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

The for цикл работает i С 1 по n, так что верхняя граница n раза (1+зарегистрируйте N), который является o(n записей N).