Вычисление количества шагов в сортировке вставки

Вот две версии сортировки вставками, которые я реализую одну из псевдокода и одну непосредственно. Я хочу знать, какая версия занимает больше шагов и места (даже немного места сложно).

void insertion_sort(int a[], int n) {
    int key, i, j;
    for(i = 1; i < n; i++) {
        key = a[i];
        j = i - 1;
        while(j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }       
}

и этот

insertion_sort(item s[], int n) {
  int i,j;
  for (i=1; i<n; i++) {
    j=i;
    while ((j>0) && (s[j] < s[j-1])) {
      swap(&s[j],&s[j-1]);
      j = j-1;
    }
  }
}

Вот пример массива сортировки a = {5, 2, 4, 6, 1, 3}. По моему мнению, вторая версия делает больше шагов, потому что она меняет номер один на один, а первая меняет местами большие числа в цикле while, а затем меняет наименьшее число. Например: Upto index = 3, обе версии предпринимают одинаковые шаги, но когда приходит index = 4, т. Е. Для замены номера 1, 2nd делает больше шагов, чем 1st. Как вы думаете?

Источник

4 ответа

Решение

"Количество шагов" не является полезной мерой чего-либо.

Является ли шаг линией? Заявление? Выражение? Инструкция на ассемблере? Микропроцессор процессора?

То есть ваши "шаги" преобразуются в ассемблер, а затем оптимизируются, и получающиеся в результате инструкции могут иметь разные (и потенциально переменные) затраты времени выполнения.

Разумные вопросы, которые вы можете задать:

1 что такое алгоритмическая сложность?

Как указано в комментарии Рэйфа Кеттлера и ответа Арпит, речь идет о том, как алгоритм масштабируется при увеличении размера входных данных.

2 как это работает

Если вы хотите знать, что быстрее (для некоторого набора входов), вам просто нужно измерить его.

Если вы просто хотите узнать, кто выполняет больше операций обмена, почему бы просто не написать swap функция, которая увеличивает глобальный счетчик каждый раз, когда он вызывается, и выяснить?

Источник

Количество свопов - неправильный термин, вы должны посчитать количество назначений. swap() расширяется до трех назначений, и поэтому вы обычно получаете больше назначений во второй версии без экономии места (у вас может не быть ключа во второй версии, но внутренне swap () имеет нечто подобное).

Источник

Обе версии используют два цикла. такая сложность O(n*n) время. Учитывая постоянное (1) время для всех остальных утверждений.

Источник

Давайте проанализируем это построчно. Я предполагаю, что сложность свопа равна 3

а) вычислительная сложность:3+(n-1)*(1+1+((n-1)/2)*(1+1+1)*(1+1)+1)=1+(n-1)*(3n)=3n^2-3n+1(Мы используем n/2, потому что оно представляется средним для непрерывных наихудших сценариев).

Память: 3 дюйма, +1 (для цикла)

б) вычислительная сложность:2+ (n-1)(1 + ((n-1)) / 2 (1 + 1 + 1)(3 + 1)) = 2+ (n-1) * (6n-5) = 6n ^ 2-11n + 7

Память:2 дюйма, + стоимость подкачки (скорее всего, дополнительно 1 целое число)

Не считая входную память, так как она одинакова в обоих случаях. Надеюсь, поможет.

Источник
Другие вопросы по тегам