В чем сложность этого псевдокода

Question

Я нашел это упражнение на экзамене и обнаружил трудность для решения проблемы.

Могу предположить наверняка, что алгоритм примет хотя бы O (n) из-за for, но я не знаю, как приблизиться к этому моменту. Я знаю, что в этом случае мне нужно оценить худшую ветвь if-else и наверняка это вторая ветвь.

for i=1...n do
    j=n
    while i<j do
        if j mod 2 = 0 then j=j-1
        else j=i

Интуитивно я думаю, что общая стоимость: O (nlogn) = O (n) * O (logn)

Answer 1

Короче говоря : цикл while будет каждый запускаться не более двух итераций.Это делает алгоритм O (n) .

Цикл while будет повторяться максимум два раза.Действительно, давайте посмотрим на цикл while:

while i < j do
    if j mod 2 = 0 then
        j=j-1
    else
        j=i

Ясно, что мы будем выполнять цикл while только если i < j.Кроме того, если j mod 2 == 1 (то есть j равно нечетное ), тогда оно установит j = i, и, следовательно, цикл while больше не будет выполняться.

Если с другой стороны j mod 2 == 0 (то есть j равно даже ), тогда мы уменьшаем j.Теперь есть две вещи, которые могут произойти, либо i == j, и в этом случае мы не выполняем дополнительную итерацию.Однако, если мы выполним дополнительную итерацию, условие if не будет выполнено, поскольку уменьшение числа четного приводит к получению числа нечетного .Поскольку мы каждый раз устанавливаем j = n, это также означает, что число шагов, которые выполняет цикл while, определяется самим n.

Это, таким образом, означает, что независимо от значений i и j, тело цикла while будет выполнено не более двух раз.

Поскольку мы выполняем цикл while явно n раз, это означает, что алгоритм все еще O (п) .Здесь мы делаем предположение, что мы можем проверить четность числа и уменьшить число в постоянное время.

Answer 2

Относится ли mod к модулю?В этом случае цикл while будет оцениваться не более двух раз;один раз для уменьшения j, но тогда j mod 2 будет 1, а после установки j=i ваш i<j будет ложным.Разница в сложности здесь колеблется, а не увеличивается с вводом, и, таким образом, для этой ветви O (1).