Измененное время и сложность пространства Mergesort - PullRequest
Новая
       16

Измененное время и сложность пространства Mergesort

0 голосов
/ 03 октября 2018

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

public static void sort(int[] a) {
  sort(a, 0, a.length - 1);
}

private static void sort(int[] a, int lo, int hi) {
  if (hi <= lo) return;

  int[] aux = new int[a.length];
  int mid = (hi + lo) / 2;
  sort(a, lo, mid);
  sort(a, mid + 1, hi);
  merge(a, lo, mid, hi, aux);
}

private static void merge(int[] a, int lo, int mid, 
 int hi, int[] aux) {

  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++)
    aux[k] = a[k];

  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      a[k] = aux[j++];
    else if (j > hi)
      a[k] = aux[i++];
    else if(aux[j] < aux[i])
      a[k] = aux[j++];
    else
      a[k] = aux[i++];
  }
}

Единственное различие между этой реализацией и типичной реализацией (которая была дана в нашем классе) состоит в том, что массив aux переопределяется при каждом рекурсивном вызове sort, а не только один раз вметод публичной сортировки в типичном случае.Типичный случай имеет время выполнения O (nlog (n)) и пространственную сложность O (n).

Моя задача - определить время и пространственную сложность показанной модифицированной реализации mergesort.Насколько я могу судить, время выполнения не изменилось, поэтому оно по-прежнему равно O (nlog (n)), а сложность пространства также равна O (nlog (n)).Моя логика заключается в том, что метод sort выделяет массив размера n каждый раз, когда он вызывается, и он называется в общей сложности log (n) раз.

До сих пор мне было трудно обдумывать пространство и временные сложности.Правильно ли я думаю об этом или нет?

Любые указатели очень ценятся.

1 Ответ

0 голосов
/ 04 октября 2018

Вы правы, сложность пространства равна O(n*logn), но требует некоторого пояснения.

Моя логика в том, что метод сортировки выделяет массив размера n каждый разон вызывается, и он называется общим количеством log (n) раз.

На самом деле, sort вызывается всего n раз во время сортировки, но максимальная глубина рекурсииlogn во время процесса.Давайте нарисуем дерево рекурсивных вызовов: 

           sort
          /    \
       sort    sort
        /\       /\
     sort sort sort sort
            ...

На каждом уровне каждая функция sort выполняет половину работы своего родителя.Так, на уровне 0 (корневой узел), sort имеет n итераций, на уровне 1 каждый из двух сортов имеет n/2 время выполнения (вместе это n), на уровне 2 каждый из четырех сортов имеет n/4 и т. Д. В совокупности каждый уровень выполняет n итераций, а поскольку глубина дерева составляет log n, вы получаете O(n*logn) сложность времени.

Однако в вашем случае aux выделяет n элементов, независимо от текущей глубины, и есть n вызовов сортировки, так что на первый взгляд можно сделать вывод, что сложность пространства равна O(n*n) = O(n^2). Это не , потому что как только мы закончим с каждым рекурсивным вызовом, выделенное пространство освобождается, и существует максимум logn рекурсивных вызовов.

Обратите внимание, что aux ненужно выделяет массивn элементов каждый раз.Вы можете улучшить алгоритм, если объявите aux в функции merge и установите соответствующую длину, примерно так: 

private static void merge(int[] a, int lo, int mid, int hi) {

  int[] aux = new int[hi - lo + 1];     

  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++)
    aux[k - lo] = a[k];

  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      a[k] = aux[j++ - lo];
    else if (j > hi)
      a[k] = aux[i++ - lo];
    else if(aux[j - lo] < aux[i - lo])
      a[k] = aux[j++ - lo];
    else
      a[k] = aux[i++ - lo];
  }
}

HTH.

...