Was bedeutet das Wort „Skalierbarkeit“ in Bezug auf Big O?

Question

Was bedeutet das Wort „Skalierbarkeit“ in Bezug auf Big O?

Infinitesimalrechnung
Algorithmen
Asymptotik
Mathematik
Realanalyse
Rechenkomplexität

Mathematikfreak

Ich bin auf viele Quellen gestoßen, die Folgendes behaupten:

Benchmarks schätzen die Laufzeit, Big O schätzt die Skalierbarkeit.

Sie erklärten die Bedeutung von "Skalierbarkeit" wie folgt:

Skalierbarkeit sagt Ihnen, wie Ihre Algorithmuslaufzeit skaliert. Das heißt, wie die Rechenzeit wächst, wenn Sie die Eingabegröße erhöhen. Für $O\left(n\right)$ Sie verdoppeln die Größe der Eingabe und verdoppeln die Rechenzeit. Für $O\left(n^2\right)$ Sie verdoppeln die Größe der Eingabe und vervierfachen die Rechenzeit und so weiter.

Das heißt, wenn Ihr Algorithmus dauert $f(n)$ Schritte im schlimmsten Fall und $f \in O\left(n^2\right)$ , dann das Verhältnis $\frac{f(2n)}{f(n)}$ ist gleich $4$ für ausreichend große Werte von $n$ (Sie verdoppeln die Eingabegröße und vervierfachen die Rechenzeit).

Und es machte so viel Sinn. Aber kürzlich wurde mir ein Gegenbeispiel gezeigt, das beweist, dass die obige Aussage einfach falsch ist. Betrachten Sie die Funktion $f\left(n\right) = n^2\left(\cos (n) + 2\right)$ . Wir können das sehen $f \in O\left(n^2\right)$ . Außerdem für diejenigen unter Ihnen, die das bemerken möchten $O\left(n^2\right)$ Leute meinen normalerweise $\Theta\left(n^2\right)$ das können wir leicht beobachten $f \in \Theta\left(n^2\right)$ sowie:

Aber $f$ skaliert nicht wie $n^2$ in dem Sinne, dass wir das nicht behaupten können $\frac{f(2n)}{f(n)}$ ist gleich $4$ (sogar ungefähr) für beliebige (auch große) Werte von n. Ich meine, wenn wir das wissen $f \in O\left(n^2\right)$ und wenn wir seine Eingabegröße verdoppeln, können wir die Rechenzeit nicht einfach vervierfachen, weil es falsch ist.

Ich habe eine Handlung erstellt $\frac{f(2n)}{f(n)}$ damit du es visualisierst:

Es sieht nicht so aus, als ob dieses Verhältnis in Richtung 4 tendiert.

Also, meine Fragen sind:

Warum erklären die Leute die Bedeutung von "Skalierbarkeit" so? Gibt es dafür einen Grund oder sind sie technisch falsch?
Was bedeutet dieses Wort "Skalierbarkeit" dann? Was genau schätzt Big O dann (wenn nicht „Skalierbarkeit“)?

Im Allgemeinen suche ich nach einer rein mathematischen Erklärung dafür. Aber machen Sie es sich bitte nicht zu schwer: Ich lerne noch eine Einvariablenrechnung. Vielen Dank an alle im Voraus!

FShrike

Es besteht ein Problem darin, dass die Limits technisch nicht existieren. Es ist klar, dass

f

$f$ Ist

Θ (n^{2})

$\Theta(n^2)$ durch die Begrenztheitsidee, aber die Grenzdefinition stellt fest, dass, während das Verhältnis der Funktionen definitiv endlich und ungleich Null ist, die Kosinusgrenze im Unendlichen (Oszillation) undefiniert ist. Ich bin mir hier nicht sicher, aber es könnte sogar Gründe geben, das zu sagen

f

$f$ ist nicht

O (n^{2})

$O(n^2)$ überhaupt durch dieses Zeichen.

Mathematikfreak

@FShrike, vielen Dank für den Kommentar. Aber

f \in O (n^{2})

$f \in O\left(n^2\right)$ nach der Definition von Big O.

FShrike

Die Idee der Skalierbarkeit wird durch Oszillation verwechselt, aber es gibt keine unmittelbare Schlussfolgerung der Skalierbarkeit aus den Grenzwertdefinitionen (obwohl ich mich jetzt daran erinnere, dass die Grenzwertdefinitionen Limit Suprema und Infima verwenden, um die Idee zu umgehen, dass die regulären Grenzwerte nicht existieren, also nehme ich zurück etwas von dem, was ich im vorherigen Kommentar gesagt habe)

Jan

1. Beispiele wie dieses wo

f \in Θ (g)

$f \in \Theta(g)$ Aber

f / g

$f/g$ ist oszillierend wie

n \to \infty

$n \to \infty$ sind in der Praxis nicht üblich. Bei diesem Verhalten fällt mir auf Anhieb nur die FFT ein, und selbst die hat eine feste Skalierung, wenn man nur mit Zweierpotenzen arbeitet. 2. Die Skalierbarkeit drückt immer noch die Wachstumsrate der Funktion grob aus, wie viel größer wird sie, wenn Sie die Eingabe um ein Bündel erhöhen. Big Theta gibt Ihnen immer noch diese grobe Beschreibung. Aber du hast recht, dass allein das Wissen, sagen wir,

f \in Θ (n^{2})

$f \in \Theta(n^2)$ sagt dir das nicht

f (2 n) / f (n)

$f(2n)/f(n)$ wird dazu tendieren

4

$4$ .

Jan

Insbesondere im Zusammenhang mit der Komplexitätstheorie interessieren sich die Menschen normalerweise entweder für Worst Cases oder für typische Fälle. Der schlimmste Fall in Ihrer Situation würde bedeuten: "Vergleichen Sie zwei Probleme, wo

n

$n$ ist nahe einem Vielfachen von

2 π

$2\pi$ "; typische Fälle würden bedeuten "vergleiche zwei Probleme wo

n

$n$ ist in der Nähe eines ungeraden Vielfachen von

π / 2

$\pi/2$ ".

Mathematikfreak

@Ian, danke für den Kommentar! Im letzten Kommentar behauptest du das

n^{2} (c o s (n) + 2)

$n^2\left(cos(n) + 2\right)$ kann nicht der schlimmste Fall sein, weil

3 n^{2}

$3n^2$ ist noch schlimmer?

Jan

Ich meine, wenn die tatsächliche Laufzeit ist

n^{2} (\cos (n) + 2)

$n^2(\cos(n)+2)$ dann der Worst Case für

n

$n$ in einem Längenintervall

2 π

$2\pi$ wird wann sein

n

$n$ ist ein Vielfaches von

2 π

$2\pi$ und in diesem Fall haben Sie

3 n^{2}

$3n^2$ .

Mathematikfreak

@Ian, aber wie ich es verstehe, gibt es keine tatsächliche Laufzeit, wenn Sie nicht zuerst den Fall angeben (am schlechtesten, durchschnittlich, am besten). Von diesem Punkt, an dem Sie es als am schlechtesten eingestuft haben, leiten Sie die Funktion ab

f (n)

$f(n)$ die eine Anzahl von Schritten darstellen, die für die Eingabe der Länge im schlimmsten Fall unternommen werden

n

$n$ . Aber wie können Sie noch weiter gehen und einzelne Punkte des Formulars angeben?

2 π k

$2πk$ um das Worst-Case-Verhalten darzustellen, wenn wir die Funktion bereits haben

f

$f$ das das Worst-Case-Verhalten darstellt?

Jan

ich meine, dass

n

$n$ ist die tatsächliche Eingabegröße und

f (n)

$f(n)$ die tatsächliche Laufzeit und

f (n)

$f(n)$ schwankt, weil irgendwie Zahlen in der Nähe von ungeraden ganzzahligen Vielfachen liegen

π

$\pi$ sind viel einfacher zu handhaben als Zahlen in der Nähe von geraden ganzzahligen Vielfachen von

π

$\pi$ (eine ungewöhnliche Situation an sich). Also das Schlimmste

n

$n$ 's einer bestimmten "Größenordnung" sind diejenigen in der Nähe

2 π k

$2\pi k$ , wenn Sie also das Wachstum im schlimmsten Fall untersuchen wollen, dann schauen Sie sich an

n = r o u n d (2 π k), k = 1, 2, \dots

$n=\mathrm{round}(2\pi k),k=1,2,\dots$ (dh

6, 13, 19

$6,13,19$ usw.)

Mathematikfreak

@Ian, aber stimmst du dem zu, wenn wir die Funktion betrachten?

f (n)

$f(n)$ das bedeutet schon jede Eingabe

n

$n$ muss das schlimmste sein? Weil

f (n)

$f(n)$ ist per Definition nur die Worst-Case-Eingaben

Jan

Nein, ich rede von den lokal schlechtesten Werten

n

$n$ (was normalerweise nicht einmal in Betracht gezogen werden muss, aber in Ihrem Fall ist es eine Sache).

Antworten (2)

Was bedeutet das Wort „Skalierbarkeit“ in Bezug auf Big O?

Es besteht ein Problem darin, dass die Limits technisch nicht existieren. Es ist klar, dass $f$ Ist $\Theta(n^2)$ durch die Begrenztheitsidee, aber die Grenzdefinition stellt fest, dass, während das Verhältnis der Funktionen definitiv endlich und ungleich Null ist, die Kosinusgrenze im Unendlichen (Oszillation) undefiniert ist. Ich bin mir hier nicht sicher, aber es könnte sogar Gründe geben, das zu sagen $f$ ist nicht $O(n^2)$ überhaupt durch dieses Zeichen.
@FShrike, vielen Dank für den Kommentar. Aber $f \in O\left(n^2\right)$ nach der Definition von Big O.
Die Idee der Skalierbarkeit wird durch Oszillation verwechselt, aber es gibt keine unmittelbare Schlussfolgerung der Skalierbarkeit aus den Grenzwertdefinitionen (obwohl ich mich jetzt daran erinnere, dass die Grenzwertdefinitionen Limit Suprema und Infima verwenden, um die Idee zu umgehen, dass die regulären Grenzwerte nicht existieren, also nehme ich zurück etwas von dem, was ich im vorherigen Kommentar gesagt habe)
1. Beispiele wie dieses wo $f \in \Theta(g)$ Aber $f/g$ ist oszillierend wie $n \to \infty$ sind in der Praxis nicht üblich. Bei diesem Verhalten fällt mir auf Anhieb nur die FFT ein, und selbst die hat eine feste Skalierung, wenn man nur mit Zweierpotenzen arbeitet. 2. Die Skalierbarkeit drückt immer noch die Wachstumsrate der Funktion grob aus, wie viel größer wird sie, wenn Sie die Eingabe um ein Bündel erhöhen. Big Theta gibt Ihnen immer noch diese grobe Beschreibung. Aber du hast recht, dass allein das Wissen, sagen wir, $f \in \Theta(n^2)$ sagt dir das nicht $f(2n)/f(n)$ wird dazu tendieren $4$ .
Insbesondere im Zusammenhang mit der Komplexitätstheorie interessieren sich die Menschen normalerweise entweder für Worst Cases oder für typische Fälle. Der schlimmste Fall in Ihrer Situation würde bedeuten: "Vergleichen Sie zwei Probleme, wo $n$ ist nahe einem Vielfachen von $2\pi$ "; typische Fälle würden bedeuten "vergleiche zwei Probleme wo $n$ ist in der Nähe eines ungeraden Vielfachen von $\pi/2$ ".
@Ian, danke für den Kommentar! Im letzten Kommentar behauptest du das $n^2\left(cos(n) + 2\right)$ kann nicht der schlimmste Fall sein, weil $3n^2$ ist noch schlimmer?
Ich meine, wenn die tatsächliche Laufzeit ist $n^2(\cos(n)+2)$ dann der Worst Case für $n$ in einem Längenintervall $2\pi$ wird wann sein $n$ ist ein Vielfaches von $2\pi$ und in diesem Fall haben Sie $3n^2$ .
@Ian, aber wie ich es verstehe, gibt es keine tatsächliche Laufzeit, wenn Sie nicht zuerst den Fall angeben (am schlechtesten, durchschnittlich, am besten). Von diesem Punkt, an dem Sie es als am schlechtesten eingestuft haben, leiten Sie die Funktion ab $f(n)$ die eine Anzahl von Schritten darstellen, die für die Eingabe der Länge im schlimmsten Fall unternommen werden $n$ . Aber wie können Sie noch weiter gehen und einzelne Punkte des Formulars angeben? $2πk$ um das Worst-Case-Verhalten darzustellen, wenn wir die Funktion bereits haben $f$ das das Worst-Case-Verhalten darstellt?
ich meine, dass $n$ ist die tatsächliche Eingabegröße und $f(n)$ die tatsächliche Laufzeit und $f(n)$ schwankt, weil irgendwie Zahlen in der Nähe von ungeraden ganzzahligen Vielfachen liegen $\pi$ sind viel einfacher zu handhaben als Zahlen in der Nähe von geraden ganzzahligen Vielfachen von $\pi$ (eine ungewöhnliche Situation an sich). Also das Schlimmste $n$ 's einer bestimmten "Größenordnung" sind diejenigen in der Nähe $2\pi k$ , wenn Sie also das Wachstum im schlimmsten Fall untersuchen wollen, dann schauen Sie sich an $n=\mathrm{round}(2\pi k),k=1,2,\dots$ (dh $6,13,19$ usw.)
@Ian, aber stimmst du dem zu, wenn wir die Funktion betrachten? $f(n)$ das bedeutet schon jede Eingabe $n$ muss das schlimmste sein? Weil $f(n)$ ist per Definition nur die Worst-Case-Eingaben
Nein, ich rede von den lokal schlechtesten Werten $n$ (was normalerweise nicht einmal in Betracht gezogen werden muss, aber in Ihrem Fall ist es eine Sache).

Vor allem Kalk · Answer 1

Dieses (sehr schöne) Beispiel ist recht ungewöhnlich - in der Praxis funktioniert es $f(n)$ die tatsächlich kommen und sind $\Theta(n^2)$ typischerweise befriedigen $f(n)/n^2$ tendiert zu einer positiven Grenze (anstatt nur davon abgegrenzt zu werden $0$ Und $\infty$ ). Also die vereinfachte Version der Skalierbarkeit - $\lim_{n\to\infty}f(2n)/f(n)$ - existiert und ist $4$ .

Aber selbst für Ihre Funktion gibt es immer noch einen vernünftigen Sinn für die Verdopplung $n$ , steigt im Durchschnitt $f(n)$ um einen Faktor von $4$ . Was können wir mit „im Durchschnitt“ meinen? Nun, um einen Durchschnitt zu nehmen, müssen Sie mehr als einmal verdoppeln. Wenn Sie zweimal verdoppeln, gehen Sie aus $f(n)$ Zu $f(4n)$ dann ist der sinnvolle durchschnittliche Skalierungsfaktor der beiden Verdopplungen das geometrische Mittel (weil Sie versuchen, sich durch geometrisches Wachstum anzunähern), dh $\sqrt{f(4n)/f(n)}$ . Nun tendiert das auch nicht zu einer Grenze, aber $\sqrt[k]{f(2^kn)/f(n)}$ , dh der (geometrische) mittlere Skalierungsfaktor aus $k$ Verdopplungen, tendiert zu einer Grenze wie $k\to\infty$ , welches ist $4$ .

Danke für die Antwort! Aber sieht es nicht so aus, als hätten wir gerade aus dem Nichts einen Weg erfunden, um die ursprüngliche Bedeutung des Wortes „Skala“ zu rechtfertigen?
Und warum ist das arithmetische Mittel in diesem Fall schlechter? Es erscheint mir ebenso vernünftig wie das geometrische Mittel.
@mathgeek Es liegt im Grunde daran, dass wir um einen Faktor skalieren $x$ und dann um einen Faktor skalieren $y$ , dann ist die Gesamtskalierung $xy$ nicht $x+y$ . Die Idee, einen Durchschnitt zu nehmen, ist „welche Liste von $k$ identische Dinge würden dieser Liste am ehesten entsprechen $k$ verschiedene Dinge?" Hier im Maßstab $k$ unterschiedliche Faktoren sollten das gleiche Gesamtergebnis ergeben wie die Skalierung mit dem "durchschnittlichen" Faktor $k$ Zeiten, und das funktioniert, wenn mit "Durchschnitt" das geometrische Mittel gemeint ist.
Eine bessere Erklärung hätte ich nicht erwarten können! Danke schön! Aber ich kann mir kaum vorstellen, dass Leute an all diese Berechnungen denken, wenn sie sagen, dass die Laufzeit „in der Größenordnung des Quadrats der Größe der Eingabe“ wächst. Würden Sie klären, was solche Leute denken (was sie eigentlich meinen), wenn sie es sagen, und ob es überhaupt legitim ist, dies zu sagen? $f$ , gegeben $f \in O(n^2)$ ?
Es ist immer noch richtig, es kann nur auf der Ebene des Vergleichs zweier bestimmter Funktionswerte fehlschlagen, wenn $f$ ist komisch. Und ich kann wirklich nicht genug betonen, wie untypisch Ihr Beispiel in der echten asymptotischen Analyse ist, insbesondere in der Komplexitätstheorie.
@Jean-ClaudeArbaut Ich verstehe nicht, warum es irreführend ist. Ich spreche speziell über das Beispiel von OP, das (wie OP ausdrücklich sagt) ein Beispiel für eine Funktion ist, die ist $\Theta(n^2)$ aber scheint nicht wie erwartet zu skalieren. Wenn Sie nur wissen, ist eine Funktion $O(n^2)$ , dann müssen Sie im zweiten Absatz grundsätzlich ersetzen $\lim$ von $\limsup$ Und $4$ von $\leq 4$ .

Faul · Answer 2

Faul

Die Landau-Symbole kümmern sich nicht um das genaue Verhalten von Funktionen. $f\in O(g)$ bedeutet das für groß $x$ wir haben $f$ Waagen höchstens so schlecht wie $g$ in dem Sinne, dass $f$ ist durch ein Vielfaches von beschränkt $g$ .

Wenn die Leute es so erklären, wie Sie es erwähnt haben, vereinfachen sie es zu sehr und gehen wahrscheinlich davon aus, dass die andere Seite sonst nicht verstehen würde, wovon man spricht.

Mathematikfreak

Danke für die Antwort! Aber wenn Sie sich meine erste Handlung ansehen, werden Sie das bemerken

f

$f$ Waage schlimmer als

n^{2}

$n^2$ im Intervall

(10; 12)

$\left(10;\ 12\right)$ Zum Beispiel. Daher skaliert es MEISTENS nicht so schlecht wie

g

$g$ ".

FShrike

@mathgeek Wir betrachten Grenzen als

n \to \infty

$n\to\infty$ in der Standarddefinition, nicht als

n \to (10, 12)

$n\to(10,12)$

Mathematikfreak

Ich habe nur ein Beispiel gegeben, damit Sie es leicht von der Handlung aus beobachten können. Aber ich bin sicher, Sie können sehen, dass meine Aussage für jeden gilt

n

$n$ (Sie können es so groß machen, wie Sie wollen).

Faul

@mathgeek Das ist einer der Vorbehalte bei der Landau-Notation. Skalierung ist ein Begriff, den wir für das Argument verwenden, das groß wird, aber wir geben nicht an, wie groß das wäre. Beachten Sie, dass wenn

f

$f$ ist stetig und

g

$g$ ist kontinuierlich und nirgendwo

0

$0$ dann finden wir in jedem abgeschlossenen Intervall immer a

c

$c$ mit

f \leq c g

$f\leq cg$ in diesem Intervall (min/max der kontinuierlichen Funktionen auf kompakten Geräten). Und selbst dann heißt es in der Definition der Landau-Symbole immer: Für alle

x > x_{0}

$x>x_0$ für einige willkürlich

x_{0}

$x_0$ . Im Grunde kümmern wir uns also nicht um endliche Werte.

Faul

Sie können sich das so vorstellen: Wenn

f \in O (g)

$f\in O(g)$ dann die Asymptotik

lim sup \frac{f (x)}{g (x)}

$\limsup\frac{f(x)}{g(x)}$ ist endlich. Wenn

f \in Θ (g)

$f\in\Theta(g)$ dann auch

0 < lim inf \frac{f (x)}{g (x)}

$0<\liminf \frac{f(x)}{g(x)}$ .

Mathematikfreak

Ja, Ihr letzter Kommentar ist die Definition, aber leider erklärt er nicht die Bedeutung des Wortes "Skala" und warum es angesichts meiner gestellten Frage sinnvoll ist.

Faul

Nun, Skalierung wird normalerweise nicht in der reinen Mathematik verwendet, sondern eher im Zusammenhang mit Algorithmen und dergleichen. Und Skalierung bedeutet hier nur: Wenn ich den Input erhöhe, wie ändert sich die benötigte Zeit. Zum Beispiel, wenn Sie eine Liste nach Größe sortieren würden

n

$n$ Die besten Algorithmen, die ohne große Annahmen funktionieren, haben eine Größenordnung von

n \log n

$n\log n$ Vergleiche. Wenn ich also meine Liste vergrößere, steigt der erforderliche Aufwand etwas mehr als linear, aber weniger als quadratisch. Natürlich gibt es mehrere Dinge, die Sie berücksichtigen können: Best Case? Schlimmsten Fall? Durchschnittlicher Fall?

Mathematikfreak

Okay, als Sie darauf hinwiesen, dass "Skalierung normalerweise nicht in der reinen Mathematik verwendet wird, sondern eher im Zusammenhang mit Algorithmen", begann es Sinn zu machen. Sie haben ein Beispiel für einen einlaufenden Algorithmus gegeben

O (\log n)

$O\left(\log n\right)$ Zeit. Könnten Sie klarstellen, was Sie mit "quadratisch ansteigen" meinen? Bitte denken Sie an das Beispiel der falschen Erklärung von "erhöht sich quadratisch", das ich in meiner Frage gegeben habe.

Was bedeutet das Wort „Skalierbarkeit“ in Bezug auf Big O?

Mathematikfreak

FShrike

Mathematikfreak

FShrike

Jan

Jan

Mathematikfreak

Jan

Mathematikfreak

Jan

Mathematikfreak

Jan

Antworten (2)

Vor allem Kalk

Mathematikfreak

Mathematikfreak

Vor allem Kalk

Mathematikfreak

Jan

Vor allem Kalk

Faul

Mathematikfreak

FShrike

Mathematikfreak

Faul

Faul

Mathematikfreak

Faul

Mathematikfreak

Was sagt Big O dir eigentlich?

Laufzeit des Algorithmus bei gegebener zeitlicher Komplexität

Algorithmuskomplexität - For-Schleife innerhalb einer While-Schleife; um den Faktor 2 abnehmen

Wie berechnet man den Wert einer multivariablen Grenze?

Wie hoch ist die zeitliche Komplexität, wenn bbb-Einträge ohne Ersatz von nnn-Einträgen einheitlich abgetastet werden?

Erwartete Zeit von Quicksort

Spivak verwendet eine Eigenschaft in seinem eigenen Beweis?

Schwache absolute Kontinuität der Maßnahmen

Gegenbeispiel zu "differenzierbar impliziert stetig"?

Darboux-Integrale mit halbierter Partition