пошаговый процесс поиска сортировки выбора большой тета-нотации

У меня возникли проблемы с определением процесса поиска большой тета-нотации для этого примера сортировки выбором. Я читал в Интернете, что и 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;
    }
};

c++ sorting time-complexity selection-sort big-theta
person Community    schedule 19.02.2015    source источник
comment
Сколько сравнений в первой итерации. Секунда? Третий? Цифры N-1, N-2, N-3...1. Теперь сложите их и посмотрите на это доказательство . Результат N(N+1)/2 - N, что составляет O(N^2) сложности. Также стоит прочитать описание алгоритма.   -  person WhozCraig    schedule 19.02.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

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

person templatetypedef    schedule 27.08.2015