Was ist die „richtige“ Definition von Ober- und Untergrenze?

19

Sei die Worst-Case-Laufzeit eines Problems bei der Eingabe der Größe n . Machen wir das Problem ein bisschen seltsam, indem wir f ( n ) = n 2 für n = 2 k, aber f ( n ) = n für n = 2 k + 1 festlegen .f(n)nf(n)=n2n=2kf(n)=nn=2k+1

  1. Wo liegt also die Untergrenze des Problems? So wie ich es verstanden habe, ist es nur die untere Grenze von . Aber wir wissen , dass f ( n ) = Ω ( n 2 ) ergibt sich, dass Konstante existiert k , n 0 , so dass für alle n > n 0 , f ( n ) > k n 2 , was nicht wahr ist. Es scheint also, dass wir nur f ( n ) = Ω ( n ) sagen könnenf(n)f(n)=Ω(n2)kn0n>n0f(n)>kn2f(n)=Ω(n). Aber normalerweise nennen wir das Problem hat eine untere Schranke von , oder?Ω(n2)

  2. Unter der Annahme , dass die , was bedeutet , dass es konstant existiert k , n 0 so daß für alle n > n 0 , g ( n ) > k n 2 . Angenommen, ein Problem hat die Laufzeit g ( n ) . Wenn wir dieses Problem für alle Primzahlen n auf ein anderes Problem (mit derselben Eingangsgröße) reduzieren können, können wir sagen, dass die Laufzeit des anderen Problems eine Untergrenze von Ω ( n) hatg(n)=Ω(n2)kn0n>n0g(n)>kn2g(n)n ?Ω(n2)

Wei Yu
quelle
12
Aus diesem Grund verwenden Mathematiker lim sup und lim inf.
Peter Shor
1
Ich glaube, ich verstehe den Unterschied. Ich denke, Post-Leute werden Omega einfach so unendlich oft verstehen. Aber falls ich eine explizite Unterscheidung treffen möchte, kann ich andere Notationen verwenden, als sie zu erweitern?
Wei Yu
3
@Wei Yu: lim sup und lim inf. Du sagst für eine Konstantewenn Sie sagen möchten, dassunendlich oft ist, und wenn Sie sagen möchtenfür alle ausreichend großen. Vor allemwenn Sie sprechen Mathematiker.
lim supg(n)n2k
g ( n ) k n 2 lim inf g ( n )kg(n)kn2g(n)kn2n
lim infg(n)n2k
g(n)kn2n
 
Peter Shor
12
@Wei: Für die meisten Komplexitätstheoretiker (siehe Lance unten) lautet Ihre Funktion θ (n ^ 2); Für die meisten Algorithmiker (siehe Knuth oder CLRS) lautet Ihre Funktion Ο (n ^ 2) und Ω (n). Beide Bezeichnungen sind in ihren Untergemeinschaften fast, aber nicht vollständig Standard; Erschwerend kommt hinzu, dass sich diese beiden Untergemeinschaften stark überschneiden! Wenn es also darauf ankommt, welche Notation Sie verwenden, müssen Sie explizit angeben, welche Notation Sie verwenden. (Zum Glück kommt es selten darauf an.)
Jeffs
2
@Jeffe. Ich glaube, Sie sollten Ihren Kommentar als Antwort posten.
Chazisop

Antworten:

13

Die richtige Definition von ist, dass es einige so dass für unendlich viele , . Die unendlich oft verwendete Definition für Untergrenzen behandelt Ihre Probleme und wird von uns in der Praxis verwendet.k > 0 n f ( n ) k n 2f(n)=Ω(n2)k>0nf(n)kn2

Ich habe 2005 einen Beitrag dazu verfasst.

Einige Lehrbücher haben diese Definition richtig, andere nicht.

Lance Fortnow
quelle
14
Knuth ist anderer Meinung als Sie: portal.acm.org/citation.cfm?id=1008329
Jeffs
4
CLRS und Wikipedia sind sich auch nicht einig. Die unendlich oft verwendete Definition ist eine bemerkenswerte Alternative, scheint jedoch weniger verbreitet zu sein.
Anonym
Ich denke, diese Definitionen stimmen alle überein, wenn die Menge der Ausnahmen Maßnahme 0 ist.
Carter Tazio Schonwald
2
f(n)=Ω(n2) f(n)=o(n+1)Ωo
András Salamon
2
oOooOn=Ω(f(n))f(n)=Ω(n2)nΩ(n2)Ω
András Salamon
4

f(n)Ω(n)

Ω(f(n))={gδ>0:n0>0:n>n0:g(n)δf(n)}.

f(n)Ω(n2)

Marcus Ritt
quelle
2

Ich kenne die am weitesten verbreitete nicht, aber ich glaube, ich kenne die älteste Verwendung (für die Informatik sowieso).

In der Arbeit von Hartmanis & Stearns aus dem Jahr 1965 "Über die Komplexität von Algorithmen" lautet die Folgerung 2.1:

UTinfnT(n)U(n)0SUST

SKO(K(n))T(n)n/kknT(n)T(n+1)

k=1

Folgerung 2.2 ist das Gegenteil von dem oben Gesagten und verwendet limit supremum, hat aber immer noch diese Anforderungen. Ich denke, da die Algorithmen mit den Jahren immer komplexer wurden, ist es möglich, dass die Anforderungen gelockert wurden.

Chazisop
quelle
2

Ich denke, wir sollten zwischen zwei Dingen unterscheiden:

  • eine Untergrenze für eine Funktion
  • eine Untergrenze für ein Problem (Algorithmus)

Wenn wir für Funktionen eine Reihenfolge festlegen, folgt daraus die Definition von Untergrenze / Obergrenze . Wenn die Ordnungsbeziehung asymptotische Majorisierung ist (konstante Faktoren ignorieren)

fg:c,nm>n. f(x)cg(x)

OΩ

Time(t(n))n2n2o(t(n))

Kaveh
quelle