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

Question

Я часто здесь говорю о Big O, который сравнивает алгоритмы друг с другом

Измеряет ли это такты или требования к пространству.

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

Answer 1

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

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

Если вы не уверены, о ком идет речь, спросите его.

Answer 2

Краткий ответ: у вас есть «Большой O в пространстве» и «Большой O во времени».

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

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

• Биг-о-о-биг-тэта

Смотри также

• Википедия / Большая буква O

Answer 8

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