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

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

Odpowiedzi: