Welche Definition der asymptotischen Wachstumsrate sollten wir vermitteln?

35

Wenn wir die Standardlehrbücher oder Tradition folgen, lehren die meisten von uns die folgenden Definition von Big-Oh - Notation in den ersten Vorlesungen eines Algorithmen Klasse: Vielleicht geben wir sogar die ganze Liste mit all ihren Quantifizierern an:

f = O (g) iff (\exists c > 0) (\exists n_{0} \geq 0) (\forall n \geq n_{0}) (f (n) \leq c \cdot g (n)) .

$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).$

$f = o(g) \mbox{ iff } (\forall c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$
$f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$
. $f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$

Da diese Definitionen jedoch nicht so einfach zu bearbeiten sind, um auch einfache Dinge wie zu beweisen,meisten von uns schnell bewegenden "Trick der Grenze" vorstellen: $5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$

, wenn vorhandenund ist , $f = o(g)$ $\lim_{n \rightarrow \infty} f(n)/g(n)$ $0$
, wenn existiert und nicht , $f = O(g)$ $\lim_{n \rightarrow \infty} f(n)/g(n)$ $+\infty$
wenn existiert und weder noch , $f = \Theta(g)$ $\lim_{n \rightarrow \infty} f(n)/g(n)$ $0$ $+\infty$
wenn existiert und nicht , $f = \Omega(g)$ $\lim_{n \rightarrow \infty} f(n)/g(n)$ $0$
wenn existiert und . $f = \omega(g)$ $\lim_{n \rightarrow \infty} f(n)/g(n)$ $+\infty$

Meine Frage ist:

Wäre es ein großer Verlust sein , die einen Bachelor - Algorithmen - Klasse für das Unterrichten der Grenzbedingungen wie nehmen die Definitionen von , , , und ? Das ist es, was wir ohnehin alle verwenden, und es scheint mir ziemlich klar, dass das Überspringen der Quantifiziererdefinitionen das Leben aller einfacher macht. $o$ $O$ $\Theta$ $\Omega$ $\omega$

Es würde mich interessieren, ob Sie auf einen überzeugenden natürlichen Fall gestoßen sind, in dem die Standard- -Definitionen tatsächlich erforderlich sind, und wenn nicht, ob Sie ein überzeugendes Argument haben, um die Standard- -Definitionen ohnehin im Voraus beizubehalten. $c,n_0$ $c,n_0$

ds.algorithms soft-question teaching Slimton
quelle

1

Das Tag sollte eigentlich "lehren", aber ich konnte kein verwandtes Tag finden und darf keine neuen Tags erstellen.

Slimton

1

Dadurch werden die Quantifizierer im Wesentlichen in die Epsilon-Delta-Definition von Grenzwerten einbezogen. Meine einzige Sorge wäre, dass viele CS-Studenten keine Analyse gemacht haben und ihr Verständnis der Grenzen daher größtenteils mechanisch ist. Damit sie jedoch schnell rechnen können, ist dies ein Kinderspiel.

Per Vognsen

6

Beachten Sie, dass Ihre beiden Definitionen von O () nicht äquivalent sind (der gleiche Vorbehalt gilt für Θ () und Ω ()). Betrachten Sie den Fall, in dem f (n) = 2n für gerade n und f (n) = 1 für ungerade n. Ist f (n) = O (n)? Ich bevorzuge limsup anstelle von lim, damit ich in diesem Fall f (n) = Θ (n) sagen kann (obwohl keine Ihrer Definitionen dies zulässt). Aber dies mag meine persönliche Präferenz sein (und sogar eine nicht standardmäßige Praxis), und ich habe noch nie eine Klasse unterrichtet.

Tsuyoshi Ito

2

@ Tsuyoshi: Ich dachte, der Punkt des "Limit-Tricks" war, dass es eine ausreichende, aber nicht notwendige Bedingung für

. (Für

es auch notwendig.) Das Oszillationsfunktions-Gegenbeispiel hat keine Begrenzung.

O ()

$O()$

o ()

$o()$

András Salamon

1

Sollten Sie nicht in jeder Definition und Eigenschaft das Symbol

durch

ersetzen ? Ich fand die Verwendung von

als Student sehr störend.

=

$=$

\in

$\in$

=

$=$

Jeremy

13

Ich bevorzuge es, die ursprüngliche Definition mit Quantifizierern zu unterrichten.

IMO, Menschen haben im Allgemeinen Probleme beim Verstehen von Formeln und Definitionen mit mehr als zwei Quantifizierungswechseln direkt. Die Einführung neuer Quantifizierer kann klarstellen, was die Definition bedeutet. Hier bedeuten die letzten beiden Quantifizierer nur "für alle ausreichend großen n", und die Einführung dieser Art der Quantifizierung kann helfen.

Die Bilder, die ich zur Erläuterung dieser Konzepte male, stimmen besser mit den Quantifiziererversionen überein.

Ich denke, die Grenzwertvereinfachung ist nützlich für Ingenieurstudenten, die nur an der Berechnung der Wachstumsrate interessiert sind, aber für Informatikstudenten nicht so nützlich sind. Tatsächlich kann die Verwendung dieser Vereinfachung mehr schaden als nützen.

Diese Idee ähnelt dem Vorschlag, dass wir die Regeln für die Berechnung von Derivaten (von Polynomen, Exponentiation, ..., Kettenregel, ...) anstelle der Epsilon-Delta-Definition verwenden, was meiner Meinung nach keine gute Idee ist.

Kaveh
quelle

Der eventuelle Herrschaft Begriff ist auch hilfreich:

genau dann , wenn

. Jetzt gilt

wenn

.

f (x) ≪ g (x)

$f(x) \ll g(x)$

\esits m \forall n > m f (n) < g (n)

$\esits m \forall n>m f(n) < g(n)$

f \in O (g)

$f \in O(g)$

c > 0

$c>0$

f (x) ≪ c g (x)

$f(x) \ll c g(x)$

Kaveh

9

Edit: Hauptrevision in Revision 3.

Da ich noch nie eine Klasse unterrichtet habe, glaube ich nicht, dass ich überzeugend behaupten kann, was wir unterrichten sollen. Trotzdem, hier sind meine Gedanken dazu.

Es gibt natürliche Beispiele, bei denen der beschriebene „Limit-Trick“ nicht angewendet werden kann. Angenommen, Sie implementieren einen „Vektor variabler Länge“ (wie Vektor <T> in C ++), indem Sie ein Array fester Länge mit doppelter Größe verwenden (dh jedes Mal, wenn Sie die Größe des Arrays überschreiten möchten, tun Sie dies Ordnen Sie das doppelt so große Array neu zu und kopieren Sie alle Elemente. Die Größe S ( n ) des Arrays, wenn wir n Elemente im Vektor speichern, ist die kleinste Potenz von 2 größer oder gleich n . Wir wollen sagen, dass S ( n ) = O ( n ) ist, aber die Verwendung des als Definition geschriebenen „Limit-Tricks“ würde uns dies nicht erlauben, weil S ( n)) / n schwingt dicht im Bereich [1,2). Gleiches gilt für Ω () und Θ ().

Wenn wir diese Notationen verwenden, um die Komplexität eines Algorithmus zu beschreiben, denke ich, dass Ihre Definition von Ω () manchmal unbequem ist (obwohl ich denke, dass diese Definition üblich ist). Es ist bequemer, f ( n ) = Ω ( g ( n )) genau dann zu definieren, wenn limsup f ( n ) / g ( n )> 0 ist. Dies liegt daran, dass einige Probleme für unendlich viele Werte von n (trivial sind. wie das perfekte Bearbeitungsproblem in einem Graphen mit einer ungeraden Anzahl n von Eckpunkten). Gleiches gilt für Θ () und ω ().

Daher finde ich persönlich, dass die folgenden Definitionen am bequemsten sind, um die Komplexität eines Algorithmus zu beschreiben: für Funktionen f , g : ℕ → ℝ _{> 0} ,

f ( n ) = o ( g ( n )) genau dann, wenn limsup f ( n ) / g ( n ) = 0. (Dies ist äquivalent zu lim f ( n ) / g ( n ) = 0.)
f ( n ) = O ( g ( n )) genau dann, wenn limsup f ( n ) / g ( n ) <∞ ist.
f ( n ) = Θ ( g ( n )) genau dann, wenn 0 <limsup f ( n ) / g ( n ) <∞ ist.
f ( n ) = Ω ( g ( n )) genau dann, wenn limsup f ( n ) / g ( n )> 0. (Dies ist äquivalent zu dem, dass f ( n ) nicht o ( g ( n )) ist.)
f ( n ) = ω ( g ( n )) genau dann, wenn limsup f ( n ) / g ( n ) = ∞ ist. (Dies ist äquivalent dazu, dass f ( n ) nicht O ( g ( n )) ist.)

oder äquivalent,

f ( n ) = o ( g ( n )) , wenn und nur wenn für jeden c > 0 ist , für ausreichend großen n , f ( n ) ≤ c ⋅ g ( n ).
f ( n ) = O ( g ( n )) , wenn und nur wenn für einige c > 0 ist , für ausreichend große n , f ( n ) ≤ c ⋅ g ( n ).
f ( n ) = Θ ( g ( n )) genau dann, wenn f ( n ) = O ( g ( n )) und f ( n ) = Ω ( g ( n )).
f ( n ) = Ω ( g ( n )) genau dann, wenn für einige d > 0, für unendlich viele n , f ( n ) ≥ d ⋅ g ( n ).
f ( n ) = ω ( g ( n )) genau dann, wenn für jedes d > 0, für unendlich viele n , f ( n ) ≥ d ⋅ g ( n ).

Aber ich weiß nicht, ob dies eine gängige Praxis ist oder nicht. Ich weiß auch nicht, ob es für den Unterricht geeignet ist. Das Problem ist, dass wir manchmal Ω () stattdessen durch liminf definieren möchten (wie Sie es in der ersten Definition getan haben). Wenn wir zum Beispiel sagen: "Die Fehlerwahrscheinlichkeit dieses randomisierten Algorithmus ist 2 - ^{Ω ( n )} ", meinen wir nicht, dass die Fehlerwahrscheinlichkeit nur für unendlich viele n exponentiell klein ist !

Tsuyoshi Ito
quelle

Ich verwende auch die limsup-Definitionen, aber für Schüler, die limsup noch nicht gesehen haben (fast alle), muss ich trotzdem explizite Quantifizierer verwenden.

Jeffs

@ JeffE: Ich stimme zu, dass die meisten Schüler Limsup noch nicht gesehen haben. Wenn wir also die Limsup-Definitionen verwenden, müssen wir stattdessen Quantifizierer in der Klasse verwenden.

Tsuyoshi Ito

2

Das Problem mit den Quantifiziererversionen ist, dass sie schwer zu merken und zu visualisieren sind. Ich ziehe

, weil sie als „höchste Grenzpunkt“ bezeichnet werden kann. Eine mögliche Erklärung ist: „Es ist wie ist

, außer dass

. Nur funktioniert , wenn die Folge konvergiert Wenn die Sequenz nicht konvergiert, zum Beispiel , weil der Algorithmus oszilliert zwischen sehr schnell für einige

und langsam für andere

, dann nehmen wir den höchsten Grenzpunkt. "

l i m s u p

$limsup$

l i m

$lim$

l i m

$lim$

n

$n$

n

$n$

Heinrich Apfelmus

Gibt es tatsächlich natürliche Beispiele für Algorithmen, bei denen die Laufzeit schwankt?

Heinrich Apfelmus

2

@Heinrich: Ich habe bereits die Laufzeit eines Algorithmus erwähnt, um eine perfekte Übereinstimmung eines Graphen mit n Eckpunkten zu finden, aber zählt dies als ein natürliches Beispiel? Ich habe ein weiteres Beispiel hinzugefügt, in dem die Laufzeit nicht oszilliert, sondern f (n) / g (n) oszilliert. Das Beispiel spricht von Raumkomplexität, aber die Zeitkomplexität desselben Beispiels hat dieselbe Eigenschaft.

Tsuyoshi Ito

8

Die Verwendung von Limits ist etwas verwirrend, da (1) dies eine kompliziertere Vorstellung ist (2) f = O (g) nicht gut erfasst wird (wie wir in der obigen Diskussion sehen können). Normalerweise spreche ich über Funktionen von den Natural-Zahlen (streng positiv) bis zu den Natural-Zahlen (die für die Laufzeit ausreichen), überspringe die kleinen Dinge, und dann ist die Definition kurz und für Studenten des ersten Studienjahres geeignet:

Dfn: f = O (g) wenn für ein C für alle n gilt f (n) <= C * g (n)

Noam
quelle

1

Erstens gefiel mir diese Definition nicht, weil die Angabe von "all n" die wichtige Tatsache verdeckt, dass die O () - Notation nur das Verhalten der Funktionen für großes n berücksichtigt. Egal für welche Definition wir uns entscheiden, ich denke, wir sollten diese Tatsache zusammen mit der Definition erläutern. Wenn man so denkt, scheint es ziemlich gut, diese einfache Definition anzugeben.

Tsuyoshi Ito

f (n) = n

$f(n) = n$

n

$n$

g (n) = 0

$g(n) = 0$

n

$n$

N_{0}

$N_0$

g (n) = f (n) + 1

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

f = O (g)

$f=O(g)$

András Salamon

2

Der Punkt, von Funktionen zu sprechen, deren Bereich die natürlichen Zahlen (ohne 0) sind, ist genau genommen kein Problem mit g (n) = 0.

Noam

1

l e n (a)

$len(a)$

\log a

$\log a$

1

a

$a$

l e n (a)

$len(a)$

\log a

$\log a$

l e n (a)

$len(a)$

a

$a$

O

$O$

\log

$\log$ , die bei einigen Eingaben verschwinden oder nicht definiert sind. "

Srivatsan Narayanan

5

$\exists c,n_0 \dots$

$f$

$f \in \mathcal{O}(g) :\Leftrightarrow \exists c,d > 0 \forall n \geq 0 : f(n) \leq c\cdot g(n) + d$ $d=f(n_0)$

Das Limit-Zeug ist ziemlich nützlich für die Berechnung von Komplexitätsklassen, also mit Stift und Papier.

In jedem Fall halte ich es für sehr nützlich, wenn die Schüler lernen, dass es eine Fülle von (hoffentlich) gleichwertigen Definitionen gibt. Sie sollten in der Lage sein, dies zu erkennen und Unterschiede bei nicht gleichwertigen Definitionen zu erkennen.

Raphael
quelle

4

Nachdem ich diese Konzepte erst vor ein paar Jahren studiert hatte, waren sie für meine Klasse nicht die schwierigsten (im Gegensatz zu Konzepten wie Induktion oder Gegenpositiven). Limits und Limsups sind meiner Meinung nach nur für diejenigen "intuitiver", die mit Kalkül vertraut sind. Studierende mit einer solchen mathematischen Grundausbildung verfügen jedoch ohnehin über einen satztheoretischen Hintergrund, sodass sie diskrete Qualifikationsmerkmale verarbeiten können.

Und was noch wichtiger ist: Denken Sie daran, dass Ihre Schüler (hoffentlich) eines Tages auch andere Lehrbücher und vielleicht sogar Forschungsarbeiten lesen werden. Daher ist es für sie besser, mit der Standardnotation auf dem Gebiet vertraut zu sein, auch wenn sie ursprünglich nicht ideal konzipiert war. Es schadet nicht, ihnen alternative Definitionen zu geben, sobald sie die Standarddefinitionen übernommen haben.

Amir
quelle

3

Schauen Sie sich Don Knuths gut geschriebenen Brief "Calculus via O notation" an , um eine interessante Darstellung des Problems zu erhalten . Er befürwortet die umgekehrte Ansicht, dass die Analysis über die Notationen 'A', 'O' und 'o' unterrichtet werden sollte.

$x$ $A$ $y$ $x = A(y)$ $|x| \leq y$ $100$ $A(200)$

Srivatsan Narayanan
quelle

1

Tsuyoshi Itos Definitionen sehen nicht ganz richtig aus. Für Little Omega und Big Omega sollte in den Definitionen liminf und nicht limsup verwendet werden. Die Definition von Big-Theta benötigt sowohl eine Untergrenze für Liminf als auch eine Obergrenze für Limsup.
Eine Definition von f (n) = O (g (n)) ist, dass es eine andere Funktion f '(n)> = f (n) gibt, so dass lim f' (n) / g (n) <unendlich ist.
Warum dürfen Neulinge Antworten posten, aber keine Kommentare abgeben?

Warren Schudy
quelle

1

Was Punkt 1 betrifft, meine ich in jedem Fall limsup, und der Grund wird im zweiten Absatz meiner Antwort erläutert.

Tsuyoshi Ito

Es ist leider ein Spam-Blocker.

Suresh Venkat

Außerdem können Sie in Ihren Antworten Latex verwenden.

Suresh Venkat

1

Zuerst versuche ich , bei den Schülern etwas Intuition zu entwickeln , bevor ich Gleichungen zeige.

"Merge-Sort vs Insertion-Sort" ist ein guter Ausgangspunkt.

f = O (G) iff (\exists c > 0) (\exists n_{0} \geq 0) (\forall n \geq n_{0}) (f (n) \leq c \cdot G (n)) .

$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).$

lim_{n \to \infty}

$\lim_{n \rightarrow \infty}$

Ein weiterer Aspekt ist, dass dies stark vom konkreten Studienprogramm abhängt. IMHO ist abhängig von den vorherigen Themen eine der Definitionen besser geeignet - IMHO empfiehlt es sich jedoch, beide zu zeigen und beide Arten von Lösungen zu akzeptieren.

Grzegorz Wierzowiecki
quelle

Welche Definition der asymptotischen Wachstumsrate sollten wir vermitteln?

Antworten: