Большой O измеряет память Requirments или просто скорость?
Я часто здесь люди говорят о Большом O, который измеряет алгоритмы друг против друга
Делает эту меру такты или необходимые площади.
Если люди хотят контрастировать алгоритмы на основе использования памяти, что мера была бы они использовать
8 ответов
Если кто-то говорит: «Этот алгоритм выполняется за O (n) время», он говорит о скорости. Если кто-то говорит: «Этот алгоритм работает в O (n) пространстве», он говорит о памяти.
Если он просто говорит: «Этот алгоритм O (n)», он обычно говорит о скорости (хотя, если он говорит это во время обсуждения памяти, он, вероятно, говорит о памяти).
Если вы не уверены, о чем идет речь, спросите его.
Большое O - это на самом деле просто мера роста сложности, основанная на росте входных данных. Два алгоритма, которые оба являются O(n), могут выполняться за совершенно разное время, но их рост линеен по отношению к росту входных данных.
Big-O можно использовать для описания взаимосвязи между любыми двумя величинами. Хотя эта концепция обычно используется только в информатике, она может быть применима и в других областях, например, в физике. Например, количество мощности, которое необходимо вложить в антенну заданного размера, чтобы получить сигнал единичной мощности на некотором расстоянии, составляет O (d ^ 2), независимо от формы антенны. Если размер антенны велик по отношению к расстоянию, требуемое увеличение силы может быть линейным или даже сублинейным, а не квадратичным, но по мере увеличения расстояния квадратичный член будет преобладать.
Краткий ответ: у вас есть «Большое О в космосе» и «Большое О во времени».
Длинный ответ: Большое О - это просто обозначение, вы можете использовать его в любом контексте. хочу.
Big O - это просто математический инструмент, который можно использовать для описания любой функции. Обычно люди используют его для описания скорости, но с тем же успехом его можно использовать для описания использования памяти.
Кроме того, когда мы используем Big O для обозначения времени, мы обычно не говорим непосредственно о тактовых циклах. Вместо этого мы считаем "базовые операции" (которые, как неявно предполагается, занимают постоянное количество циклов).
Хотя обычно алгоритмы конкурируют по времени, я обычно предполагаю, что любой оператор O был временем. Тем не менее, вполне допустимо также сравнивать пространство. O можно использовать для любых измерений - мы просто обычно используем скорость, потому что она обычно наиболее важна.
Обычно это количество операций, которое переводится в скорость. Обычно алгоритмы различаются больше по скорости, чем по использованию памяти. Однако при необходимости вы увидите, что для использования памяти используется нотация O ().
Big O и другие используются для измерения роста чего-либо.
Когда кто-то говорит, что что-то имеет O(N), значит, это что-то растет не быстрее линейной скорости. Если что-то является Ω(N^2), то эта вещь растет не медленнее квадратичной скорости. Если что-то есть Θ(2^N), то эта вещь растет с экспоненциальной скоростью.
Что это за вещь, может быть требованием времени для алгоритма. Это может быть также требование к пространству, т.е. памяти для алгоритма. Это также может быть практически все, что угодно, не связанное ни с пространством, ни со временем.
Например, некоторые массивно параллельные алгоритмы часто измеряют масштабируемость в количестве процессоров, на которых они могут работать. Определенный алгоритм может выполняться на O(N) процессорах за O(N^2) время. Другой алгоритм может работать на O(N^2) процессорах за O(N) время.