пошаговый процесс нахождения выбора сортировки большой тэта нотации

Question

пошаговый процесс нахождения выбора сортировки большой тэта нотации

У меня возникли проблемы с определением процесса нахождения большой тэта-нотации для этой выборки. Я читал в интернете об этом и о том, что вложенные циклы tl; dr означают, что это будет = O (n ^ 2), однако, я не знаю, как они это получили. Мне нужен пошаговый процесс поиска нотации, то есть добавление стоимости операций и всего остального. было бы хорошо, если бы кто-то сделал это для этого примера кода, чтобы я мог понять это более четко. Заранее спасибо…

void select(int selct[])
{
int key;
int comp;
for (int i = 0; i < 5; i++)
{
key = i;
for (int j = i + 1; j < 5; j++)
{
if (selct[key] > selct[j])
{
key = j;
}
}
comp = selct[i];
selct[i] = selct[key];
selct[key] = comp;
}
};

0

big-theta c++selection-sort sorting time-complexity

Решение

Другие решения

Источник

Accepted Answer

Анализируя временную сложность алгоритма, я нахожу его полезным для не посмотрите на код и вместо этого подумайте об основной идее, управляющей алгоритмом. Если вы концептуально знаете, что делает алгоритм, часто проще определить сложность времени, просто подумав, что будет делать алгоритм, а затем выведя из этого сложность времени.

Давайте применим этот подход здесь. Так как именно работает сортировка выбора? Ну, это начинается с нахождения минимального значения в последних n элементах и его замены на позицию 0, затем нахождения минимального значения в последних n — 1 элементах и замены его на позицию 1, а затем нахождения минимального значения в последних n — 2 элемента и замена его в положение 2 и т. Д.

«Жесткая часть» алгоритма — выяснить, какой из последних n — k элементов наименьший. Сортировка выбора делает это путем итерации по этим элементам и сравнения каждого с элементом, который в настоящее время известен как самый маленький. Это требует n — k — 1 сравнений.

Посмотрим, сколько сравнений. На первой итерации нам нужно сделать n — 1 сравнений. На второй итерации мы проводим n — 2 сравнения. На третьем мы делаем n — 3 сравнения. Суммирование количества сравнений дает нам хороший способ измерения общей работы:

(n — 1) + (n — 2) + (n — 3) + … + 3 + 2 + 1 = n (n — 1) / 2

Это известное суммирование — его стоит запомнить, и оно говорит нам, сколько сравнений требуется. Количество сделанных сравнений является отличным показателем общего объема проделанной работы. Так как есть n (n — 1) / 2 = n² / 2 — n / 2 = Θ (n²) в сравнении, временная сложность выбора вида Θ (n²).

0