Является ли реализация сортировки вставкой наихудшим вариантом O (n)?

Я знаю, что сортировка вставок должна быть наихудшим вариантом O (n ^ 2), но мне интересно, почему следующая реализация не является O (n).

void main()
{
//insertion sort runs from i = 1 to i = n, thus is worst case O(n)
for (

    int i = 1,
    placeholder = 0,
    A[] = { 10,9,8,7,6,5,4,3,2,1 },
    j = i;

    i <= 10;

    j-- > 0 && A[j - 1] > A[j]
    ? placeholder = A[j], A[j] = A[j - 1], A[j - 1] = placeholder
    : j = ++i
)

{
for (
    int x = 0;
    x < 10; x++
) 
    cout << A[x] << ' ';
    cout << endl;
}


system("pause");
}

Здесь задействован только один цикл for, и он работает от 1 до n. Мне кажется, что это будет определение O (n). Что именно мне здесь не хватает?

-8
задан JaMiT 23 August 2019 в 05:49
поделиться

1 ответ

Неаккуратная терминология привела многих людей к ложным выводам. Это, кажется, пример.

существует только один для цикла, включенного здесь, и он работает от 1 до n.

Да, существует только один цикл, но что это "он", к которому Вы обращаетесь? Я действительно имею в виду, чтобы Вы думали об этом. "Это" должно относиться к циклу? Это соответствовало бы довольно общему, все же неаккуратному, использованию терминологии, но цикл не оценивает к значению. Таким образом, цикл не может на самом деле работать от одного значения до другого. Небрежность может быть пропущена в более простых контекстах, но не в Вашем.

Обычно, "это" действительно относилось бы к контрольная переменная цикла . С простым циклом, как for (int i = 0; i < 10; ++i), существует взаимно-однозначное соответствие между повторениями цикла и оценивает присвоенный контрольной переменной (который является i в моем примере). Таким образом, существует существующая эквивалентность, позволяя один относиться к циклу, когда каждый действительно имеет в виду контрольную переменную. Высказывание, что цикл работает от x до y действительно, означает, что контрольная переменная выполнения от x до y, и что существует одно повторение цикла на значение, присвоенное контрольной переменной . Эта корреспонденция перестала работать в Вашем коде.

В Вашем цикле, вещь, которая работает от 1 до n, i. Однако i не увеличен с каждым повторением цикла, таким образом, "это работает от 1 до n", не точная оценка Вашего цикл . Когда i 1, существует до 2 повторений. Это не взаимно-однозначное соответствие между повторениями и значениями i. Как i увеличения, растет расхождение от непосредственного. Каждое значение i потенциально соответствует i+1 повторения, как j количества по сравнению с [1 110] к [1 111]. Общее количество повторений в худшем варианте развития событий для n записей является суммой потенциального количества повторений для каждого значения [1 112]: 2  + 3  + ⋯ + (n+1) = (n²   +   3n)/2. Это - O (n²).

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

0
ответ дан 6 September 2019 в 19:20
поделиться
Другие вопросы по тегам:

Похожие вопросы: