Ausdruck O(N^2) < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:21 Sa 13.11.2021 | | Autor: | senmeis |
Hi,
in Softwaretechnik ist ein Ausdruck [mm] O(N^2) [/mm] zu merken der sich auf Speicherbedarf beziehen sollte. Ist dieser der standardisierte Ausdruck? Was ist [mm] N^2?
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:06 Sa 13.11.2021 | | Autor: | fred97 |
> Hi,
>
> in Softwaretechnik ist ein Ausdruck [mm]O(N^2)[/mm] zu merken der
> sich auf Speicherbedarf beziehen sollte. Ist dieser der
> standardisierte Ausdruck? Was ist [mm]N^2?[/mm]
>
Schau nach bei Google unter Landausymbole
|
|
|
| |
|
Der Ausdruck ist in der Programmiertechnik ein Maß für den Rechenaufwand eines Algorithmus. Dieser kann sich auf die Rechenzeit und/oder den Speicheraufwand beziehen und bedeutet folgendes:
N=Anzahl der Daten
O=Verhalten des Aufwandes.
O(N) bedeutet: Der Aufwand ist etwa proportional zur Datenmenge, also doppelte Datenmenge [mm] \hat= [/mm] doppelter Rechenzeit und/oder doppeltem Speicheraufwand.
[mm] O(N^2) [/mm] bedeutet: Der Aufwand wächst etwa quadratisch mit der Datenmenge.
Beispiel: N Daten sollen paarweise miteinander verglichen werden. Der Speicheraufwand beträgt O(N) (doppelt so viele Daten - doppelt soviel Speicher), der Rechen-/Zeitaufwand aber [mm] O(N^2). [/mm] Bei 4 Daten hast du die Vergleiche 1-2, 1-3, 1-4, 2-3, 2-4 und 3-4, also 6 Vergleiche.
Bei 8 Daten hast du 7 Vergleiche 1-x, 6 Vergleiche 2-x, ... 1 Vergleich 7-8, also 7+6+5+4+3+2+1=28 Vergleiche, also mehr als 4 mal so viel. Die Formel dafür lautet
N*(N-1)/2 = [mm] N^2/2-N/2, [/mm] wobei bei großen N (und nur das wird betrachtet) N/2 gegenüber [mm] N^2/2 [/mm] vernachlässigt werden kann.
Als die Rechner um 1980 noch viel langsamer waren, habe ich folgende Simulation durchgeführt:
Es wurden 1200 Pseudonamen erzeugt, indem für jeden Namen ein Salat aus 25 Buchstaben erwürfelt wurde. Der Vorgang dauerte ca. 4 Minuten.
Danach wurden die Namen alphabetisch mit dem Programm "Bubblesort" [mm] (O(N^2)) [/mm] sortiert. Nach einer halben Stunde unterbrach ich das Programm und rechnete hoch, wie lange es insgesamt dauern würde. Ich kam auf ca. 9 Stunden.
Danach sortierte ich dasselbe nochmals mit Quicksort (O(N*log(N))). Es war in 3,5 Minuten fertig. Beide Lösungen stimmten überein.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:44 Mo 13.12.2021 | | Autor: | senmeis |
Ich habe auch [mm] Omega(n^3) [/mm] gesehen. Ist dieses gleich wie [mm] O(n^3)?
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:44 Mo 13.12.2021 | | Autor: | Infinit |
Hallo senmeis,
es gibt hier unterschiedlice Notationen, die auch eine Aussage darüber enthalten, welche Größe wie schnell wächst.
Diese unterschiedlichen Bezeichnungen findest Du ![[]](/images/popup.gif) hier
Viele Grüße,
Infinit
|
|
|
|
