Каково «правильное» определение верхних и нижних границ?

19

Пусть $f(n)$ будет временем выполнения задачи на входе размера в худшем случае $n$ . Давайте сделаем задачу немного странной, установив $f(n) = n^2$ для $n=2k$ но $f(n) = n$ для $n=2k+1$ .

Итак, какова нижняя граница проблемы? Насколько я понял, это просто нижняя граница $f(n)$ . Но мы знаем, что $f(n) = \Omega(n^2)$ означает, что существует постоянная $k$ , $n_0$ такая, что для всех $n > n_0$ , $f(n) > kn^2$ , что неверно. Таким образом, кажется, что мы можем только сказать $f(n) = \Omega(n)$ , Но обычно мы будем называть проблему нижней границей $\Omega(n^2)$ , верно?
Предполагая, что $g(n) = \Omega(n^2)$ , это означает, что существует постоянная $k$ , $n_0$ такая, что для всех $n > n_0$ , $g(n) > kn^2$ . Давайте также предположим, что проблема имеет время выполнения $g(n)$ . Если мы можем свести эту проблему для всех простых чисел $n$ к другой задаче (с тем же размером ввода), можем ли мы сказать, что время выполнения другой задачи имеет нижнюю границу $\Omega(n^2)$ ?

cc.complexity-theory time-complexity Вэй Ю
источник

12

Вот почему математики используют lim sup и lim inf.

Питер Шор

1

Поэтому я думаю, что понимаю разницу. Я думаю, что почтовые люди будут просто понимать Омегу как бесконечно часто. Но если я хочу сделать явное различие, есть ли какие-либо обозначения, которые я могу использовать, кроме расширения?

Вэй Ю,

3

lim sup \frac{g (n)}{n^{2}} \geq k

$\limsup \frac{g(n)}{n^2} \geq k$

k

$k$

g (n) \geq k n^{2}

$g(n) \geq k n^2$

lim inf \frac{g (n)}{n^{2}} \geq k

$\liminf \frac{g(n)}{n^2} \geq k$

g (n) \geq k n^{2}

$g(n) \geq k n^2$

n

$n$

$\$

12

@Wei: Для большинства теоретиков сложности (см. Ланс ниже) ваша функция θ (n ^ 2); Для большинства алгоритмистов (см. Кнут или CLRS) ваша функция Ο (n ^ 2) и Ω (n). Обе нотации почти, но не полностью, стандартны в своих подсообществах; что еще хуже, эти два сообщества сильно пересекаются! Поэтому, если имеет значение, какую нотацию вы используете, вы должны четко указать, какую нотацию вы используете. (К счастью, это редко имеет значение.)

Джеффс

2

@ Джефф. Я считаю, что вы должны оставить свой комментарий в качестве ответа.

Chazisop

13

Правильное определение состоит в том, что существует некоторое такое, что для бесконечного числа , . Бесконечно часто встречающееся определение нижних границ решает ваши проблемы и показывает, как мы используем его на практике. $f(n)=\Omega(n^2)$ $k>0$ $n$ $f(n)\geq kn^2$

Я сделал пост по этому вопросу еще в 2005 году.

Некоторые учебники дают правильное определение, а некоторые нет.

Лэнс Фортноу
источник

14

Кнут с вами не согласен: portal.acm.org/citation.cfm?id=1008329

Джефф

4

CLRS и Wikipedia также не согласны с вами. Определение «бесконечно часто» является заслуживающей внимания альтернативой, но, похоже, используется менее широко.

Аноним

я думаю, что все эти определения согласуются, когда набор исключений является мерой 0.

Картер Тацио Шонвальд

2

Проблема с определениями «бесконечно часто» состоит в том, что они обычно не исключают «бесконечно часто». Таким образом, мы имеем ужасное следствие, что с этим определением но также и , где и означают строгие порядки в некоторых смысл. Мне действительно не нравится это. По крайней мере, предложение @ Carter об исключениях из меры 0 немного менее ужасно, но все же допускает более тонкий порядок, чем обычный.

f (n) = Ω (n^{2})

$f(n)=\Omega(n^2)$

f (n) = o (n + 1)

$f(n)=o(n+1)$

Ω

$\Omega$

o

$o$

Андрас Саламон

2

@Jukka: Нет, я злоупотребляя здесь. Как вы намекаете, я должен исправить свой аргумент, чтобы использовать вместо . Поэтому позвольте мне изложить фактическое возражение без использования или . С «бесконечно часто», каждый имеет аномалию, что , , но . Так что даже не формирует предзаказ.

o

$o$

O

$O$

o

$o$

o

$o$

O

$O$

n = Ω (f (n))

$n = \Omega(f(n))$

f (n) = Ω (n^{2})

$f(n) = \Omega(n^2)$

n \neq Ω (n^{2})

$n \ne \Omega(n^2)$

Ω

$\Omega$

Андрас Саламон

4

С определением Кнута вы можете утверждать только . Как вы заметили, это не интуитивно понятно и происходит для функций, которые Витани и Меертенс называют «дикими». Они предлагают определить $f(n)\in\Omega(n)$

Ω (f (n)) = {g ∣ \exists δ > 0 : \forall n_{0} > 0 : \exists n > n_{0} : g (n) \geq δ f (n)} .

$\Omega(f(n))=\{ g \mid \exists \delta>0:\forall n_0>0:\exists n>n_0: g(n)\geq \delta f(n)\}\textrm{.}$

(Это то же самое, что и определение Ланса.) С этим определением . $f(n)\in\Omega(n^2)$

Маркус Ритт
источник

2

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

В статье Хартманиса и Стернса "О вычислительной сложности алгоритмов", написанной в 1965 году, следствие 2.1:

Если и такие функции времени, что то $U$ $T$ $\inf_{n \rightarrow \infty} \frac{T(n)}{U(n)} \geq 0$ $S_{U} \subseteq S_{T}$

где - класс сложности всех задач, вычислимых в . T (n) должен подчиняться для некоторого целого числа и всех и , но оно не должно быть конструируемым по времени. $S_{K}$ $O( K(n) )$ $T(n) \geq n/k$ $k$ $n$ $T(n) \leq T(n+1)$

Ваша функция подчиняется первому правилу для но не подчиняется второму правилу. $k = 1$

Следствие 2.2 является ответом на вышесказанное и использует верхний предел, но все еще имеет эти требования. Я предполагаю, что с годами алгоритмы усложнялись, возможно, что требования были смягчены.

chazisop
источник

2

Я думаю, что мы должны различать две вещи:

нижний предел для функции
нижний предел для проблемы (алгоритм)

Для функций, когда мы фиксируем порядок, из него следует определение нижнего / верхнего предела . Если отношение порядка является асимптотическим мажорированием (без учета постоянных факторов)

f ⪯ g : \exists c, n \forall m > n . f (x) \leq c g (x)

$f \preceq g : \exists c,n \forall m>n. \ f(x) \leq c g(x)$

тогда определение является обычным определением и . Оба они широко используются в других областях, таких как комбинаторика. $O$ $\Omega$

Но когда мы говорим о нижней границе задачи (алгоритме), мы действительно хотим сказать, что проблема требует определенного количества ресурсов (для запуска алгоритма, решающего проблему). Часто классы сложности параметризуются такими функциями, как , и мы просто говорим, что задача ограничена снизу функцией, но это работает только для хороших функций (например, время выполнения алгоритма является монотонным и т. д.). Что мы хотим сказать в этих случаях, так это то, что нам нужно времени выполнения для решения проблемы, т. Е. Меньше времени работы недостаточно, что формально становится определением Ланса, что время выполнения алгоритма не . $\mathbf{Time}(t(n))$ $n^2$ $n^2$ $o(t(n))$

Кава
источник

Каково «правильное» определение верхних и нижних границ?

Ответы: