Сложность пространства-времени в варианте голландского национального флага

Вариант ДНФ выглядит следующим образом:

def dutch_flag_partition(pivot_index , A):
    pivot = A[pivot_index]
    # First pass: group elements smaller than pivot.
    for i in range(len(A)):
      # Look for a smaller element.
        for j in range(i + 1, len(A)):
           if A[j] < pivot:
             A[i], A[j] = A[j], A[i]
             break

# Second pass: group elements larger than pivot.

for i in reversed(range(len(A))):
    if A[i] < pivot:
      break
    # Look for a larger element. Stop when we reach an element less than
    # pivot , since first pass has moved them to the start of A.
    for j in reversed(range(i)):
       if A[j] > pivot:
         A[i], A[j] = A[j], A[i]
         break

Дополнительная пространственная сложность задается как O (1). Это потому, что обмен не зависит от длины ввода? И временная сложность, заданная как O (N ^ 2), связана ли она с вложенными циклами? Спасибо


python time-complexity space-complexity dutch-national-flag-problem
person srkdb    schedule 02.08.2018    source источник
comment
Обмен не создает никакого дополнительного пространства вообще. У вас есть немного места для некоторых других вещей, таких как pivot, range и его итератор, i и т. д., и все они, очевидно, постоянны. (Если это не Python 2, в этом случае диапазон линейный…)   -  person abarnert    schedule 02.08.2018

Ответы (2)


arrow_upward
1
arrow_downward

Дополнительная пространственная сложность задается как O (1). Это потому, что обмен не зависит от длины ввода?

Нет. На самом деле подкачка вообще не занимает лишнего места.

Что еще более важно, вы не можете просто найти что-то одно и сказать, сколько бы это ни стоило, в этом сложность. Вы должны просматривать все элементы, и самый большой элемент определяет сложность. Итак, просмотрите все, что вы создаете:

  • pivot — это просто ссылка на один из членов списка, который имеет постоянный размер.
  • range - постоянный размер.
  • итератор над range имеет постоянный размер.
  • целочисленные значения i и j, возвращаемые итератором диапазона, имеют постоянный размер.1
  • …

Поскольку нет ничего большего, чем постоянный размер, общий размер является постоянным.

И временная сложность, заданная как O (N ^ 2), связана ли она с вложенными циклами?

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

И опять же, вы должны все сложить, а не просто взять что-то одно и угадать.

Итак, первый проход делает:

  • Простой список, индексация и назначение, константа.
  • A loop over the input length.
    • … with a loop over the input length
    • … с некоторым индексированием списков, сравнениями и присваиваниями, все постоянные
    • … который также рано прерывается в некоторых случаях … к чему мы можем вернуться.

Итак, если break совсем не помогает, то это O(1 + N * N * 1), то есть O(N * N).

И второй проход аналогично O(N * (1 + N * 1)), который снова O(N * N).

А если добавить O(N * N + N * N), получится O(N * N).

Кроме того, даже если break сделает первый проход лог-линейным или что-то в этом роде, O(N * log N + N * N) все равно будет O(N * N), так что это не имеет значения.

Итак, время квадратично.

1. Технически это не совсем так. Целые числа имеют переменный размер, и память, которую они занимают, является логарифмом их величины. Итак, i и j, а также атрибуты stop объектов range и, возможно, некоторые другие вещи - все log N. Но если вы не имеете дело с арифметикой с огромными целыми числами, как в криптоалгоритмах, которые умножают огромные простые множители, люди обычно игнорируют это и сходят с рук.

person abarnert    schedule 02.08.2018

arrow_upward
1
arrow_downward

Дополнительная пространственная сложность задается как O (1). Это потому, что обмен не зависит от длины ввода?

Поскольку вы «просто» меняете местами, новые данные не создаются и не генерируются, вы просто переназначаете значения, которые у вас уже есть, поэтому сложность пространства постоянна.

И временная сложность, заданная как O (N ^ 2), связана ли она с вложенными циклами?

Истинный. Это полиномиальная временная сложность второго порядка, потому что у вас есть два вложенных цикла for.

У вас в них break, поэтому в более благоприятных случаях ваша временная сложность будет ниже N^2. Однако, поскольку большой-0 — это наихудший случай, можно сказать, что это степень 2.

person DarkCygnus    schedule 02.08.2018