Не должна ли пространственная сложность сортировки вставки быть O (N)?

Question

Это покрывает «программный алгоритм» от https://stackoverflow.com/help/on-topic

Это является из лекционного слайде из класса

Вот реализация вставки рода, что мы использовали

public static void insertionSort(int[] a) { 
    for (int i = 1; i < a.length; i++) { 
      int temp = a[i]; 
      int j = i; 
      while (j >= 1 && a[j - 1] > temp) { 
       a[j] = a[j - 1]; 
     } 
     a[j] = temp; 
    } 
} 

Я согласен что пространственная сложность локальных переменных будет равна O (1), поскольку каждый раз, когда размер входного файла равен одному, каждый из них принимает одинаковые локальные переменные, i, j и temp будут занимать блок памяти.

Однако я смущен пространственной сложностью массива. http://www.cs.northwestern.edu/academics/courses/311/html/space-complexity.html был подобный пример,

int sum(int a[], int n) { 
    int r = 0; 
    for (int i = 0; i < n; ++i) { 
     r += a[i]; 
    } 
    return r; 
} 

и отметил, что этот алгоритм требует N блоков памяти для а, то есть его пространство сложность O (N)?

Что это? O (N), потому что для массива потребуется N единиц памяти (зависит от размера ввода) или O (1) из-за передачи по ссылке?

Answer 1

Array passed by reference означает, что вы сортируете на месте, без дополнительно пространство необходимо для выходных данных.

Поэтому пространство сложности (то, что вам нужно сверх исходных данных устанавливается ^(а)) является константой O(1), а не линейный O(n).

С точки зрения конечного фрагмента кода, который слишком является O(1) просто потому, что массивы деградируют до первоклассников элементов указателей при передаче функции. Автор, похоже, понимает концепцию с их комментарием в нижней части страницы:

Но будьте осторожны. Если вещи передаются указателем или ссылкой, то пространство является общим. Если A передает массив C-стиля в B, то не будет выделено новое пространство.

Но, по какой-то причине, они, похоже, считают, что передача массива будет сделать копию ^(б).

---

^(а) Если пространство сложности должны были включать в исходный набор данных, то O(1) сложность будет невозможно.

---

^(б) И, так как самый лучший человек в состоянии говорить от имени автора является самим автором, я протянул руку с вопросом, а ответ объясняет различие между этими двумя случаями.I надежда он не возражает, поскольку, будучи педагогом, я предполагаю, что он имеет такое же отношение «увеличение-общий-знание-в-мире», как я, и это демонстрирует уровень уважения к такому отношению, которое Я нашел освежающий:

Дополнительное пространство обычно называют вспомогательной космической сложности. Без квалификатора сложность пространства включает требования к пространству ввода.

На моей странице, по крайней мере, указывается это различие. Лучшая страница показала бы простые практические примеры того, как алгоритмы торгуют временем, пространством и простотой алгоритма, но поскольку я не преподавал курс данных в течение многих лет, я не вернулся, чтобы поддерживать любую из этих страниц , И я никогда не претендую на роль эксперта в теории сложности. Естественное понимание языка, основанные на случаях рассуждения и гибкая разработка программного обеспечения - мои сильные стороны.

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

Спасибо, что обратились ко мне, и я надеюсь, что это поможет.

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

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

Однако, я буду немного более конкретными в будущем, обеспечивая Заявляю, что я имею в виду космической сложности в случае, если читатели не уверены :-)

В любом случае, что по крайней мере проясняет, почему ваш примечания к курсу и замечания Северо-Западного отличаются в своих утверждениях. Независимо от того, какое определение сложности пространства вы выберете, один из них должен быть скорректирован с учетом этого.

Answer 2

В сущности оба курса согласны.

С северо-западной части связанной страницы:

Если функция А использует M единиц своего собственного пространства (локальные переменные и параметры), и она вызывает функцию B, которая нуждается N единиц локального пространства, то Общие потребности M + N единиц временного рабочего пространства. Что делать, если A называет B 3 раза? Когда функция заканчивается, ее пространство может быть повторно использовано, поэтому, если A называет B 3 раза, ему все еще нужны только единицы измерения M + N.

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

Применяя это к вашему примеру, массив приходит из функции который вызывает В (здесь функция sum), и передает ему массив. sum не выделяет и не создает массив, и не нужно его копировать, поэтому он не учитывается в том, что требуется sum.

Answer 3

Я считаю, что автор с северо-запада неверен. Пространство, используемое для функции, зависит от того, сколько пространства передано функции, но сколько места выделяется в функции во время ее использования.

В примере суммы пространство выделяется до вызова функции и не выделяется внутри функции, поэтому она будет рассчитывать на использование пространства.