Требует ли Big O измерения памяти или просто скорость?

Ответ 1

Если кто-то скажет: "Этот алгоритм работает в O (n) раз", он говорит о скорости. Если кто-то говорит: "Этот алгоритм работает в O (n) пространстве", он говорит о памяти.

Если он просто говорит: "Этот алгоритм O (n)", он обычно говорит о скорости (хотя, если он говорит об этом во время обсуждения памяти, он, вероятно, говорит о памяти).

Если вы не знаете, о ком кто-то говорит, спросите его.

Ответ 2

Короткий ответ: у вас есть "Big O in space" и "Big O in time".

Длинный ответ: Big O - это всего лишь обозначение, вы можете использовать его в любом контексте.

Ответ 3

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

Кроме того, когда мы используем Big O для времени, мы обычно не говорим напрямую о тактовых циклах. Вместо этого мы подсчитываем "основные операции" (которые неявно предполагают, что они принимают постоянное число циклов).

Ответ 4

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

Ответ 5

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

Ответ 6

Big-O может использоваться для описания взаимосвязи между любыми двумя величинами. Хотя это, как правило, используется только в информатике, концепция может также применяться в других областях, таких как физика. Например, количество мощности, которое должно быть помещено в антенну заданного размера, чтобы получить сигнал удельной мощности на некотором расстоянии, равно O (d ^ 2), независимо от формы антенны. Если размер антенны большой по отношению к расстоянию, увеличение требуемой прочности может быть линейным или даже сублинейным, а не квадратичным, но по мере увеличения расстояния будет доминировать квадратичный член.

Ответ 7

Big O и другие используются для измерения роста чего-то.

Когда кто-то говорит, что что-то есть O(N), тогда эта вещь растет не быстрее линейной скорости. Если что-то есть Ω(N^2), то эта вещь растет не медленнее, чем квадратичная скорость. Когда что-то есть Θ(2^N), тогда эта вещь растет с экспоненциальной скоростью.

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

Например, некоторые массивно-параллельные алгоритмы часто измеряют масштабируемость в количестве процессоров, на которых он может работать. Конкретный алгоритм может выполняться на O(N) процессорах в O(N^2) времени. Другой алгоритм может работать на процессорах O(N^2) в O(N) времени.

Связанные вопросы

• Big-oh vs big-theta

См. также

• Википедия/примечание Big O

Ответ 8

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