Время выполнения этой программы

В настоящее время я изучаю курс «Введение в Java» и готовлюсь к среднесрочному обучению. Я столкнулся с этой проблемой:

public void wug() {
    int j = 0;
    for (int i = 0; i < N; i += 1) {
        for (; j < M; j += 1) {
            if (bump(i, j))
                break;
        }
    }
}

N и M тривиальны и указаны где-то еще.

В решении указано время выполнения if theta (M + N) для худшего случая и theta (N) для лучшего случая. Я понимаю лучший случай, но я думал, что худший случай - тета (N * M). Может ли кто-нибудь объяснить, почему наихудший случай - это тета (M + N)? Я действительно сомневаюсь в сложности алгоритма. Спасибо!


runtime asymptotic-complexity
person lewis.k    schedule 10.11.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Обратите внимание, что j никогда не сбрасывается, поэтому внутренний цикл повторяется не более M раз. Чтобы получить N*M итераций, вам нужно сбросить итератор на ноль в начале цикла.

person JJJ    schedule 10.11.2015
comment
Ах, я это пропустил. Спасибо! - person lewis.k; 11.11.2015

arrow_upward
0
arrow_downward

Обратите внимание, что j не инициализируется во внутреннем цикле, поэтому каждое выполнение внутреннего цикла продолжается с того места, где завершился предыдущий цикл. Подумайте, как это меняет различные значения, которые j принимает во время выполнения программы.

Вы лучше поймете этот код, настроив его в отладчике и пройдя через него пошагово. Это потому, что вы видите то, что, по вашему мнению, делает код, а не то, что на самом деле происходит. Пошаговое выполнение кода помогает сосредоточиться на деталях, которые имеют значение.

person christutty    schedule 10.11.2015