Анализ алгоритма сортировки оболочки (большой O) - PullRequest
Новая
       5

Анализ алгоритма сортировки оболочки (большой O)

0 голосов
/ 03 марта 2020

Это алгоритм сортировки оболочки. 

  void shellSort(int array[], int n){
    for (int gap = n/2; gap > 0; gap /= 2){
        for (int i = gap; i < n; i += 1) {
           int temp = array[i];
           int j;

           for (j = i; j >= gap && array[j - gap] > temp; j -= gap){
              array[j] = array[j - gap];
           }
           array[j] = temp;
        }
      }
  }

Я уверен, что внешний l oop этого алгоритма выполняется logn раз, но я не уверен с средний l oop и самый внутренний l oop. Этот сайт https://stackabuse.com/shell-sort-in-java/ сказал, что средняя l oop пробегает n-промежуток раз, в то время как самый внутренний l oop пробегает i / gap , но я ' Я не уверен в этом. Пожалуйста, помогите мне понять, как работает центральный и внутренний l oop в этом алгоритме, большое спасибо всем, кто помог мне в этом.

Ответы [ 3 ]

3 голосов
/ 03 марта 2020

Это циклы в алгоритме: 

for (int gap = n/2; gap > 0; gap /= 2) {
  for (int i = gap; i < n; i += 1) {
    for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
    }
  }
}

Давайте начнем с l oop over i. Он начинается с gap и продолжается до n с шагом 1. Следующее значение l oop сверх j начинается с тока i и понижается на gap, пока не станет меньше gap. Таким образом, l oop over j выполняется один раз для i между gap и 2*gap, дважды для i между 2*gap и 3*gap, три раза для i между 3*gap и 4*gap и тд.

Это означает, что j l oop будет выполняться один раз для gap различных значений i, дважды для gap различных значений i, три раза для gap различных значения i, et c.

Максимальное значение для i равно n, поэтому значение l oop сверх j может выполняться максимально j_max = (n - gap)/gap раз. Общее количество выполнений j l oop равно 

1+1+...+1+1 + 2+2+...+2+2 + 3+3+...+3+3 + .... + j_max+j_max+...+j_max+j_max
|_________|   |_________|   |_________|          |_________________________|
 gap times     gap times     gap times                    gap times

Эта сумма равна 

gap*(sum from 1 to j_max) = gap * j_max(j_max + 1) / 2 = O(gap * ((n-gap)/gap)^2) = O((n-gap)^2/gap)

Это будет повторяться для различных значений gap в внешний l oop, поэтому сложность O-big составляет 

sum((n-gap)^2/gap, for gap = n/2, n/4, n/8, ...., 4, 2, 1)

Расширение: 

(n^2 - 2*n*gap + gap^2)/gap = n^2*(1/gap) - 2*n + gap

Первый член равен n в квадрате, умноженном на следующие значения: 

1/(n/2),  1/(n/4),  1/(n/8), ..... 1/4,  1/2, 1/1

или 

2/n, 4/n, 8/n, ....., n/n

Это сумма степеней двух, деленная на n, поэтому первый член дает всего 

n^2/n * 2^(log2 n) = n^2

. второй член равен -2*n, суммированному log2 n раз, поэтому сложность равна 

n*log2 n

Последний член равен сумме gaps, так что это сумма степеней двух и его сложность n. Объединяя все вместе, мы получаем сложность наихудшего случая как O (n ^ 2).

1 голос
/ 03 марта 2020

Формула для нахождения числа членов в арифметической последовательности c имеет вид (последний член - первый член) / разность + 1

for (int i = gap; i < n; i += 1) начинается с i = пробел и выходит при i == n , Последнее значение, которое я могу принять, это n - 1.

Каждый l oop, i увеличивается на 1, поэтому этот l oop выполняется (n - 1 - пробел) / 1 + 1 = n - времена разрыва

for (j = i; j >= gap && array[j - gap] > temp; j -= gap)

Этот l oop начинается с j = 1 и завершается, когда j <пробел (игнорируйте вторую часть, предполагая наихудший случай senario). Последнее значение, которое может принять j, - это пробел. </p>

Каждый l oop, j уменьшается на пробел, поэтому это l oop выполняется (i - пробел) / gap + 1 = i

1 голос
/ 03 марта 2020

В каждой итерации середина l oop начинается в промежутке и заканчивается в n. Таким образом, общее количество итераций будет n - разрыв

Внутренний разрыв начинается с i. На каждой итерации оно уменьшается на разрыв. Предположим, что i = 15 и gap = 3, тогда значения j на последующих итерациях будут 15,12,9,6,3. Что составляет 5 итераций. Поэтому i / gap итераций в худшем случае.

...