matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgorithmen und DatenstrukturenAusdruck O(N^2)
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Algorithmen und Datenstrukturen" - Ausdruck O(N^2)
Ausdruck O(N^2) < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ausdruck O(N^2): Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]


        
Bezug
Ausdruck O(N^2): Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Ausdruck O(N^2): Antwort
Status: (Antwort) fertig Status 
Datum: 19:13 Sa 13.11.2021
Autor: HJKweseleit

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.



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]