Что это означает, когда предусмотрено, что дополнительное разрешенное пространство O (1)?

Ответ 1

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

Некоторые компиляторы могут выполнять оптимизацию хвостовых вызовов (TCO) и удалять рекурсивные вызовы, если они являются последним оператором, выполняемым в любом заданном кодовом пути через функцию. При использовании TCO накладные расходы памяти, связанные с стеклом, не связаны.

Однако имейте в виду, что ограничение O (1) может быть навязано, чтобы заставить вас выбрать конкретный (вероятно, нерекурсивный) алгоритм, поэтому полагаться на оптимизацию хвостового вызова может быть неразумно, даже если вы знаете компилятор, используются, сделали соответствующее преобразование в ваш код. По крайней мере, если вы полагаетесь на это, вы должны сказать это явно и оправдать свое ожидание того, что TCO будет происходить со ссылкой на спецификации языка, документацию компилятора и/или дизассемблирование по мере необходимости.

Ответ 2

extra allowed space is O(1)

означает, что ваша программа может использовать только постоянное пространство, скажем C.

Следуя определению big-O, это означает, что пространство, в котором нуждается ваша программа, не может зависеть от размера ввода, хотя C можно сделать сколь угодно большим.

Итак, если рекурсия зависит от ввода ^a (что обычно имеет место), то пространство, которое требуется вашей программе, не O(1).

Для уточнения:

Программа, которая всегда использует 1 Mb, использует пространство O(1).

Программа, которая всегда использует 1 Tb, использует O(1) space ^b.

Программа, которая использует N Mb, где N - это вход, не использует пробел O(1) (использует пробел O(N)).

Короче говоря, всякий раз, когда вы читаете O(1), просто мысленно замените его на константу.

а. Например, foo (n) = foo (n - 1), пространство стека, необходимое для поддержания вызовов функций, это O(N)

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

Ответ 3

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

Ответ 4

Что касается других ответов, говорящих вам, что количество стека, которое вы должны использовать, равно O(1) и должно оставаться постоянным независимо от размера ввода, если вы хотите решить проблему рекурсивным образом, это приведет к тому, что вы две возможности:

• Рекурсия с фиксированной глубиной, что означает ограничение количества времени, которое функция рекурсирует.
• Tail-recursion, что означает, что рекурсивный вызов функции должен быть последним, что нужно оценить, чтобы вызвать TCO. (оптимизация хвостового вызова) Грубо говоря, это означает, что, поскольку рекурсивный вызов является последним, что происходит в исполнении funciton, вместо того, чтобы нажимать контекст вызова в стеке, существующий контекст вызова будет перезаписан новым, эффективно используя константу количество пространства стека.

Ответ 5

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

Я согласен с принятым ответом, но хочу отметить, что если вы используете язык с tail оптимизация звонков (например, clojure), тогда вы можете решить проблемы с пространством O(1), которое будет использовать больше пространства с языком, который не имеет этой функции (например, java).

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

Ответ 6

Сложность хранения O (1) просто означает, что алгоритм должен использовать постоянный объем хранилища. т.е. он должен использовать один и тот же объем памяти на множестве из 10 элементов, как и на 1000.

Вероятно, вы должны использовать итерацию для выполнения этого.