Отмена ртутного толчка
Краткое объяснение: Если алгоритм имеет значение Θ (g (n)), это означает, что время работы алгоритма с ростом n (размер ввода) становится пропорциональным g (n).
Если алгоритм имеет O (g (n)), это означает, что время работы алгоритма с ростом n больше не более , пропорциональное g (n).
blockquote> Обычно, даже когда люди говорят о O (g (n)), они фактически означают Θ (g (n)), но технически, есть разница.
Более технически:
O (n) представляет верхнюю границу. Θ (n) означает жесткую привязку. Ω (n) - нижняя граница.
f (x) = Θ (g (x)), если f (x) = O (g (x)) и f (x ) = Ω (g (x))
blockquote> blockquote> В основном, когда мы говорим, что алгоритм имеет O (n), это также O (n2), O (n1000000), O (2n), ... но алгоритм Θ (n) не является Θ (n2).
На самом деле, поскольку f (n) = Θ (g (n)) означает для достаточно больших значений n, f (n) могут быть связаны в пределах c1g (n) и c2g (n) для некоторых значений c1 и c2, т. е. скорость роста f асимптотически равна g: g может быть нижней границей и верхней границей of f. Это непосредственно означает, что f может быть нижней границей и верхней границей g. Следовательно,
f (x) = Θ (g (x)) iff g (x) = Θ (f (x))
blockquote> для отображения f (n) = Θ (g (n)), достаточно показать, что g является верхней границей f (т. е. f (n) = O (g (n))), а f - нижняя грань g ( т.е. f (n) = Ω (g (n)), что является тем же самым, что g (n) = O (f (n))). В частности,
f (x) = Θ (g (x)), если f (x) = O (g (x)) и g (x) = O (f (x)))
blockquote>
Также имеются небольшие о-о и мало-омега (ω), обозначающие свободные верхние и свободные нижние границы функции.
Подводя итог:
f(x) = O(g(x)) (big-oh) означает, что скорость роста f(x) асимптотически меньше или равна к скорости роста g(x).
f(x) = Ω(g(x)) (big-omega) означает, что скорость роста f(x) асимптотически больше или равна роста скорость g(x)
f(x) = o(g(x)) (little-oh) означает, что скорость роста f(x) асимптотически меньше темпа роста g(x).
f(x) = ω(g(x)) (мало-омега) означает, что скорость роста f(x) асимптотически больше темпа роста g(x)
f(x) = Θ(g(x)) (theta) означает, что скорость роста f(x) асимптотически равна темпа роста g(x)
blockquote> . Для более подробного обсуждения вы можете читайте определение в Википедии или обратитесь к классическому учебнику, например, «Введение в алгоритмы» Cormen и др.
Если алгоритм имеет значение Θ (g (n)), это означает, что время работы алгоритма с ростом n (размер ввода) становится пропорциональным g (n).
Если алгоритм имеет O (g (n)), это означает, что время работы алгоритма с ростом n больше не более , пропорциональное g (n).
blockquote>Обычно, даже когда люди говорят о O (g (n)), они фактически означают Θ (g (n)), но технически, есть разница.
Более технически:
O (n) представляет верхнюю границу. Θ (n) означает жесткую привязку. Ω (n) - нижняя граница.
f (x) = Θ (g (x)), если f (x) = O (g (x)) и f (x ) = Ω (g (x))
blockquote> blockquote>В основном, когда мы говорим, что алгоритм имеет O (n), это также O (n2), O (n1000000), O (2n), ... но алгоритм Θ (n) не является Θ (n2).
На самом деле, поскольку f (n) = Θ (g (n)) означает для достаточно больших значений n, f (n) могут быть связаны в пределах c1g (n) и c2g (n) для некоторых значений c1 и c2, т. е. скорость роста f асимптотически равна g: g может быть нижней границей и верхней границей of f. Это непосредственно означает, что f может быть нижней границей и верхней границей g. Следовательно,
f (x) = Θ (g (x)) iff g (x) = Θ (f (x))
blockquote>для отображения f (n) = Θ (g (n)), достаточно показать, что g является верхней границей f (т. е. f (n) = O (g (n))), а f - нижняя грань g ( т.е. f (n) = Ω (g (n)), что является тем же самым, что g (n) = O (f (n))). В частности,
f (x) = Θ (g (x)), если f (x) = O (g (x)) и g (x) = O (f (x)))
blockquote>Также имеются небольшие о-о и мало-омега (
ω), обозначающие свободные верхние и свободные нижние границы функции.Подводя итог:
f(x) = O(g(x))(big-oh) означает, что скорость ростаf(x)асимптотически меньше или равна к скорости ростаg(x).
f(x) = Ω(g(x))(big-omega) означает, что скорость ростаf(x)асимптотически больше или равна роста скоростьg(x)
f(x) = o(g(x))(little-oh) означает, что скорость ростаf(x)асимптотически меньше темпа ростаg(x).
f(x) = ω(g(x))(мало-омега) означает, что скорость ростаf(x)асимптотически больше темпа ростаg(x)blockquote>
f(x) = Θ(g(x))(theta) означает, что скорость ростаf(x)асимптотически равна темпа ростаg(x). Для более подробного обсуждения вы можете читайте определение в Википедии или обратитесь к классическому учебнику, например, «Введение в алгоритмы» Cormen и др.