Jaka jest „właściwa” definicja górnej i dolnej granicy?

19

Niech będzie najgorszym czasem działania problemu na wejściu wielkości . Uczyńmy ten problem nieco dziwnym, ustalając dla ale dla . $f(n)$ $n$ $f(n) = n^2$ $n=2k$ $f(n) = n$ $n=2k+1$

Więc jaka jest dolna granica problemu? Zrozumiałem, że to tylko dolna granica . Ale wiemy, że oznacza, że istnieje stała , taka, że dla wszystkich , , co nie jest prawdą. Wydaje się więc, że możemy powiedzieć tylko . Ale zwykle nazywamy problem dolną granicą , prawda? $f(n)$ $f(n) = \Omega(n^2)$ $k$ $n_0$ $n > n_0$ $f(n) > kn^2$ $f(n) = \Omega(n)$ $\Omega(n^2)$
Zakładając, że , co oznacza, że istnieje stała , taka, że dla wszystkich , . Załóżmy również, że problem ma czas działania . Jeśli możemy zmniejszyć ten problem dla wszystkich liczb pierwszych do innego problemu (przy tym samym rozmiarze wejściowym), czy możemy powiedzieć, że czas działania innego problemu ma dolną granicę ? $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

— Wei Yu
źródło

12

Dlatego matematycy używają lim sup i lim inf.

— Peter Shor,

1

Więc myślę, że rozumiem różnicę. Myślę, że post użytkownicy będą rozumieli Omegę tak często. Ale w przypadku, gdy chcę wprowadzić wyraźne rozróżnienie, czy mogę użyć innych zapisów niż rozwinąć je?

— Wei Yu

3

@Wei Yu: lim sup i lim inf. Mówisz dla jakiegoś stałego

jeśli chcesz powiedzieć, że

nieskończenie często, i

jeśli chcesz powiedzieć

dla wszystkich odpowiednio dużych

.

Zwłaszcza jeśli rozmawiasz z matematykami.

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$

$\$

— Peter Shor,

12

@Wei: Dla większości teoretyków złożoności (patrz Lance poniżej), twoją funkcją jest θ (n ^ 2); dla większości algorytmów (patrz Knuth lub CLRS), twoją funkcją jest Ο (n ^ 2) i Ω (n). Oba oznaczenia są prawie, ale nie całkowicie, standardem w ich społecznościach podrzędnych; co gorsza, te dwie podspołeczności mocno się pokrywają! Więc jeśli ma to znaczenie, które notacja używać, to trzeba powiedzieć wyraźnie których notacja używasz. (Na szczęście rzadko ma to znaczenie.)

— Jeffε

2

@Jeffe. Uważam, że powinieneś opublikować swój komentarz jako odpowiedź.

— chazisop

13

Prawidłowa definicja jest taka, że istnieje pewne takie, że dla nieskończenie wielu , . Nieskończenie często definicja dolnych granic obsługuje Twoje problemy i określa, w jaki sposób używamy jej w praktyce. $f(n)=\Omega(n^2)$ $k>0$ $n$ $f(n)\geq kn^2$

Napisałem o tym post w 2005 roku.

Niektóre podręczniki mają tę definicję, inne nie.

— Lance Fortnow
źródło

14

Knuth nie zgadza się z tobą: portal.acm.org/citation.cfm?id=1008329

— Jeffε

4

CLRS i Wikipedia również nie zgadzają się z tobą. Nieskończenie często definicja jest godną uwagi alternatywą, ale wydaje się, że jest rzadziej stosowana.

— Anonimowy

myślę, że wszystkie te definicje są zgodne, gdy zbiorem wyjątków jest miara 0.

— Carter Tazio Schonwald

2

Problem z definicjami „nieskończenie często” polega na tym, że zwykle nie wykluczają „nieskończenie często nie”. Mamy więc okropną konsekwencję, że z tą definicją ale także , gdzie i mają być ścisłymi porządkami w niektórych sens. Naprawdę nie lubię tego. Przynajmniej sugestia @ Cartera o wyjątkach miary 0 jest nieco mniej okropna, a jednocześnie pozwala na lepsze zamówienie niż zwykle.

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

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

f (n) = o (n + 1)

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

Ω

$\Omega$

o

$o$

— András Salamon,

2

@Jukka: Nie, ja nadużywania tutaj. Jak sugerujesz, muszę poprawić mój argument, aby użyć zamiast . Niech mi zatem przekształcić rzeczywisty sprzeciw bez użycia lub . W przypadku „nieskończenie często” anomalia polega na tym, że , , a jednak . Tak więc nawet nie tworzy przedsprzedaży.

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$

— András Salamon

4

Dzięki definicji Knutha możesz twierdzić tylko . Jak widać, nie jest to intuicyjne i zdarza się, że funkcje Vitányi i Meertens nazywają „dzikimi”. Proponują zdefiniowanie $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{.}$

(Jest to to samo, co definicja Lance'a). Przy tej definicji . $f(n)\in\Omega(n^2)$

— Marcus Ritt
źródło

2

Nie wiem o najczęściej używanych, ale wydaje mi się, że znam najstarsze użycie (w każdym razie do informatyki).

W artykule Hartmanisa i Stearnsa z 1965 r. „O złożoności obliczeniowej algorytmów” następstwem 2.1 jest:

Jeśli i są funkcjami czasowymi takimi, że to $U$ $T$ $\inf_{n \rightarrow \infty} \frac{T(n)}{U(n)} \geq 0$ $S_{U} \subseteq S_{T}$

gdzie jest klasą złożoności wszystkich problemów obliczalnych w . T (n) musi być zgodny z dla jakiejś liczby całkowitej oraz wszystkich i , ale nie musi być konstruowany w czasie. $S_{K}$ $O( K(n) )$ $T(n) \geq n/k$ $k$ $n$ $T(n) \leq T(n+1)$

Twoja funkcja przestrzega pierwszej reguły dla ale nie przestrzega drugiej reguły. $k = 1$

Następstwem 2.2 jest wzajemność powyższego i wykorzystuje limit supremum, ale nadal ma te wymagania. Wydaje mi się, że z biegiem lat algorytmy stawały się coraz bardziej złożone, możliwe jest, że wymagania zostały złagodzone.

— chazisop
źródło

2

Myślę, że powinniśmy rozróżnić dwie rzeczy:

dolne ograniczenie dla funkcji
dolna granica problemu (algorytm)

W przypadku funkcji, gdy ustalamy porządek, wynika z niego definicja dolnego / górnego ograniczenia . Jeśli relacją rzędu jest asymptotyczna dominacja (ignorowanie stałych czynników)

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)$

wtedy definicja jest zwykłą definicją i . Oba są szeroko stosowane w innych obszarach, takich jak kombinatoryka. $O$ $\Omega$

Ale kiedy mówimy o dolnej granicy dla problemu (algorytmu), tak naprawdę chcemy powiedzieć, że problem wymaga pewnej ilości zasobów (do uruchomienia algorytmu rozwiązującego problem). Często klasy złożoności są parametryzowane przez funkcje takie jak , a my po prostu mówimy, że problem jest ograniczony przez funkcję, ale działa to tylko dla ładnych funkcji (np. Czas działania algorytmu jest monotoniczny itp.). Co chcemy powiedzieć w tych przypadkach jest to, że musimy czas pracy, aby rozwiązać problem, czyli mniej niż Czas pracy nie jest wystarczające, który formalnie staje definicję Lance, że czas działania algorytmu nie jest w . $\mathbf{Time}(t(n))$ $n^2$ $n^2$ $o(t(n))$

— Kaveh
źródło