Что делает это означает: O (n) шаги и O (1) пространство?

Question

Что делает это означает: O (n) шаги и O (1) пространство?

Что делает O (1) среднее пространство? Я понимаю, что O (n) шаги похож на порядок величины вычислений, которые делает алгоритм/программа, но не знайте, каков O (n) пространство.

26

computer-science

задан Bill the Lizard 19 September 2012 в 12:24

2 ответа

По сути, «O (n) шагов и O (1) пространство» будет означать, что количество шагов, выполняемых алгоритмом, линейно масштабируется (O (n)) с количеством элементов, но объем памяти, который он занимает, является постоянным. .

1

ответ дан 28 November 2019 в 07:16

Другие вопросы по тегам:

computer-science

Похожие вопросы:

score 44 · Accepted Answer

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

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

Edit : Добавление двух примеров:

Bubblesort требует пространства O(1).
Слияние требует пробела O(n).