Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Inhaltsverzeichnis

1. Drei Elemente der Datenstruktur

1.1 Operationen an Datenstrukturen

1.2 Speicherstruktur der Datenstruktur

2. Datentyp, abstrakter Datentyp

3. Algorithmus

3.1 Zeitkomplexität T(n)

3.2 Raumkomplexität

---

1. Drei Elemente der Datenstruktur

1.1 Operationen an Datenstrukturen

Das heißt, hinzufügen, löschen, ändern und überprüfen

1.2 Speicherstruktur der Datenstruktur

2. Datentyp, abstrakter Datentyp

Art der Daten:

(1). Atomtyp: bool, int...

(2). Strukturtyp: Klasse, Struktur ...

Abstrakter Datentyp (ADT):

Ähnlich wie Strukturtypen, BenutzerNurSie müssen die Datenstruktur kennenNameund die Verbindungen zwischen ihren Daten (Funktion) dürfen

3. Algorithmus

3.1 Zeitkomplexität T(n)

Je kleiner die Zeitkomplexität, desto besser ist der Algorithmus

(1). Betriebsregeln

Zusatz:

Mehrere Elemente hinzufügenBei wird nur der Term höchster Ordnung (Potenz) beibehalten

T1(n) + T2(m) = T(max(n,m))

Multiplikation:

T1 x T2 = O(f(n) xg(n))

(2). Gemeinsame Größenordnungsvergleiche

Im Allgemeinen reicht es aus, sich an die ersten drei und die letzten drei zu erinnern –Oft bezieht sich die Macht auf die Bestellung 

3.2 Raumkomplexität

1 GB = 1024 * 1024 * 1024 Bytes sind etwa 1 Milliarde

1 GB = 1024 MB, 1 MB = 1024 KB, 1 KB = 1024 Byte

Tatsächlich ist es nicht erforderlich, die Anzahl der in verschiedenen Datentypen gespeicherten Bytes zu kennen. Speichern Sie sie einfach direkt als Zahlen. Schließlich werden die Koeffizienten weggelassen und in eine Berechnungsformel umgewandelt, die n mit einem Koeffizienten von enthält eins.

In der Funktion, alsParameterAlle eingehenden Daten sindKeine Notwendigkeitwird zur Raumkomplexität gezählt, da die Anzahl dieser Parameter bekannt ist und weggelassen werden kann (außer bei rekursiven Funktionen)

In der Funktion müssen diese berechnet werdenIn einer Funktion erzeugt die DeklarationVariablen.

besonders:

In der rekursiven Funktion werden die Daten jedes Mal übergeben, undwird nicht abgedecktan seinem ursprünglichen Standort, aber gespeichert inneue AdresseWenn Sie also die Raumkomplexität einer rekursiven Funktion bestimmen möchten, müssen Sie sich über die Speichernutzung des gesamten Prozesses vom Startpunkt bis zum Endpunkt der Rekursion im Klaren sein.

Insbesondere wenn es um rekursive Funktionen auf Arrays gehtArrayvonLängetritt bei Rekursion aufÄndern, dann ist es oft notwendig zu verwendenArithmetische Folgesumme，