Могут ли некоторые помочь мне с функцией, которая является Big O (1), но не Ω (1), и наоборот? Некоторое объяснение очень поможет.
Функция, которая является Big O (1), но не Ω (1)
comment
когда функция будет O (1), но не Ω (1)? Подумайте, что означает каждое из них.
- person aaronasterling schedule 26.09.2010
comment
Поскольку O (1) - константа, не может быть функции, которая ограничена сверху O (1). Вот что я думаю ...
- person rda3mon schedule 26.09.2010
comment
Это связано с stackoverflow.com/questions/3209139/
- person andand schedule 27.09.2010
Ответы (1)
Большой O означает ‹=, а большой Omega означает> =, поэтому функция, которая равна O (1), но не Omega (1), - это f (n) = 1 / n. С другой стороны, f (n) = n работает.
person
Keith Randall
schedule
26.09.2010
@Keith: Как вы могли когда-либо построить алгоритм, делающий дробное количество шагов?
- person Michael Madsen; 26.09.2010
Вы не можете. Но вопрос был не в этом.
- person Keith Randall; 26.09.2010
Тогда, во-первых, это правильный вопрос?
- person rda3mon; 26.09.2010
Хорошая уловка, я тоже думал об алгоритме. +1.
- person IVlad; 26.09.2010
Вопрос совершенно справедливый, если вы говорите только о функциях. Однако, если функция представляет время работы алгоритма, оно должно быть не менее 1. В любом случае обратное (Omega (1), но не O (1)) совершенно верно.
- person Keith Randall; 26.09.2010
Тогда я ошибся, пометив это в алгоритмах. Но, как мне кажется, поскольку O (1) является константой, как она может ограничивать любую кривую. Или может быть просто Theta (1) всего лишь константа? Я только начинаю с алгоритмов, пожалуйста, не задавайте глупых вопросов
- person rda3mon; 26.09.2010
@Ringo: O (1) - это набор. А именно множество ограниченных функций. И n - ›1 / n (для натуральных чисел n) является членом этого множества. Ω (1) - другое множество, а именно множество функций, отделенных от нуля, и n - ›1 / n не является членом этого множества. Теперь, поскольку время работы алгоритма не может каким-либо разумным образом (что я мог себе представить) уменьшаться с большими входными данными, в контексте алгоритмической сложности, разумно рассматривать алгоритмы с временем выполнения в O (1) как требующий практически постоянного времени.
- person Christopher Creutzig; 26.09.2010
Итак, Theta Θ (1) должна быть константой, я прав? Это развеяло многие мои сомнения. Спасибо Кристоферу Кройцигу, Кейту Рэндаллу и другим.
- person rda3mon; 26.09.2010
Кроме того, насколько я понимаю, O (1) и Ω (1) являются дизъюнктными множествами, это правильно?
- person rda3mon; 26.09.2010
@Ringo: Нет, Θ (1) = O (1) ∩ Ω (1) - это множество всех функций f, которые имеют конечный ненулевой предел. Что для алгоритмической сложности «по существу постоянное». (Строго говоря, Θ (1) - это, конечно, константа. Постоянный набор функций. В том же смысле, что функция sin является константой - сама функция не изменяется…)
- person Christopher Creutzig; 26.09.2010
Хорошо, я понял вашу точку зрения. Это было очень полезно ... Спасибо. У меня есть еще одно сомнение: в книге Cormen по алгоритмам я читал, что Θ (n ^ 0) совпадает с Θ (1). Как это возможно, если Θ (1) = O (1) ∩ Ω (1), так как O (1) имеет n ^ (1/2) в качестве своей функции?
- person rda3mon; 26.09.2010
@Ringo, меня смущает твой вопрос. В O (1) нет n ^ (1/2). n ^ (1/2) растет с увеличением n. Но n ^ (1/2) находится в Омеге (1).
- person Keith Randall; 27.09.2010
Ладно, я понял. Я был сбит с толку, прежде чем задать этот вопрос. Теперь мне это показалось ясным. Спасибо
- person rda3mon; 27.09.2010
@MichaelMadsen AFAIK Существуют алгоритмы квантовых вычислений, которые могут выполнять вычисления быстрее, чем объем данных - поиск в n элементах за время O (sqrt (n)). Пока это все еще теоретически, потому что такое квантовое оборудование еще не создано, алгоритмы находятся в процессе работы. (В настоящее время создаваемые адиабиатические квантовые компьютеры являются лишь одним из возможных типов).
- person Grzegorz Wierzowiecki; 11.01.2012
