Функция порядка и роста циклов

Question

Я пытаюсь найти порядок и функцию роста этого для l oop внутри функции, которая принимает массив длиной n > 2.

Эта функция упорядочивает массив в порядке возрастания. Я пытаюсь найти порядок для наихудшего сценария: когда массив изначально упорядочен в порядке убывания, и поэтому функция должна много раз перебирать массив, чтобы отсортировать его.

Вот l oop:

        for (int next = 1; next < array.length; next++) {
            int value = array[next];
            int index = next;
            while (index > 0 && value < array[index - 1]) {
                array[index] = array[index - 1];
                index--;
            }
            array[index] = value;
        }

Я ломал себе голову, пытаясь понять это. Пишу тесты, записываю тонны функций, и я приближаюсь, но никогда не сразу. Как бы вы go через такой al oop могли найти его функцию порядка и роста?

Любое направление было бы очень признательно. Большое вам спасибо.

Answer 1

Пусть n будет длиной массива. Это l oop имеет наихудшее время работы O (n ^ 2). Вот простой способ увидеть это:

Когда next = 1, количество операций, выполняемых while l oop, не больше 1. Когда next = 2, количество операций не больше 2 и так далее, пока next = (n - 1). Мы можем игнорировать другие операции, выполняемые for l oop, потому что они представляют собой члены более низкого порядка, которые не имеют отношения к росту.

Итак, теперь количество операций равно k * (1 + 2 + 3 + 4 + ... + (n - 1)) = k * (n * (n - 1) / 2) = k n ^ 2 - k n / 2, где k - постоянный коэффициент.

Следовательно, рост функции имеет порядок n ^ 2.

Редактировать:

Чтобы ответить на комментарий, мы обычно не учитываем всего количество инструкций, потому что для этого нет стандарта.

Например, будете ли вы считать одну итерацию следующего l oop одним оператором (одним оператором печати) или двумя операторами (оператором печати и увеличением i)?

for (int i = 0; i < n; i++)
{
    print(i);
}

Вдобавок это откровенно не очень полезный метри c. В большинстве случаев нас интересует только член алгоритма наивысшего порядка.

Однако, чтобы ответить на ваш вопрос, я бы посчитал l oop как выполнение этих многих операторов: 2n ^ 2 + 2n - 3 .