пошаговый процесс поиска выбор сортировка big theta нотация

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; 
    } 
}; 

Answer 1

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

Давайте применим этот подход здесь. Итак, как точно работает сортировка? Ну, он начинается с нахождения минимального значения в последних 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

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