Leela Krishna
Leela Krishna

Folgen

Apr 1, 2019 · 4 min Lesezeit

in swift Programmiersprache…

Teil -1:

Warum Datenstrukturen?

Bei der Erstellung moderner Apps wird ein Großteil der Algorithmen innewohnenden Theorie oft übersehen. Bei Lösungen, die relativ kleine Datenmengen verbrauchen, sind Entscheidungen über bestimmte Techniken oder Entwurfsmuster möglicherweise nicht wichtig, da nur die Dinge zum Laufen gebracht werden. Wenn das Publikum wächst, werden auch die Daten wachsen. Ein Großteil dessen, was große Technologieunternehmen tun, ist ihre Fähigkeit, große Datenmengen zu interpretieren. Daten sinnvoll zu nutzen, ermöglicht es Benutzern, Transaktionen zu verbinden, zu teilen, abzuschließen und Entscheidungen zu treffen.

→ Datenstrukturen :

  • Grundlegende (elementare) Datenstrukturen

Stapel, Warteschlange, Sortieralgorithmen

  • Bäume

Bäume & Binärbäume, Binäre Suche, Heap, Heap-Sortierung, Prioritätswarteschlange

  • Graphen

Graphen, Adjazenzliste, Dijkstra-Algorithmus, Prim-Algorithmus

→ Big O-Notation :

Asymptotische Analyse ist der Prozess der Beschreibung der Effizienz von Algorithmen und wird üblicherweise in einem gängigen Format ausgedrückt, das als Big O-Notation bekannt ist.

  • Zeitkomplexität :

Die Zeit, die benötigt wird, um den Algorithmus (die Funktion) abzuschließen, wenn seine Eingabegröße (n) zunimmt.

  • Raumkomplexität :

Die Menge an Speicher (Speicherplatz), die für die Ausführung eines Algorithmus (einer Funktion) benötigt wird.

Beide können in Big O-Notation ausgedrückt werden.

  • Häufigste Zeitkomplexitäten :

→ Konstante Zeit (O(1)) :-

Ein Algorithmus mit konstanter Zeit hat unabhängig von seiner Eingabe die gleiche Laufzeit. Die große O-Notation dafür ist O (1).

→ Lineare Zeit (O(n)) :-

Ein linearer Zeitalgorithmus ist, dessen Geschwindigkeit von seiner Eingabegröße abhängt. Mit anderen Worten, es wird weniger effizient, wenn seine Eingabegröße (n) wächst.

→ Quadratische Zeit (O(n2)) :-

es bezieht sich auf einen Algorithmus, der Zeit benötigt, um proportional zum Quadrat der Eingabegröße zu sein. Es gerät schnell außer Kontrolle, wenn die Eingabegröße zunimmt.

→ Logarithmische Zeit (O(log n)) :-

Ein üblicher Algorithmus mit O (log n) -Zeitkomplexität ist die binäre Suche, deren rekursive Beziehung T(n / 2) + O(1) ist, dh auf jeder nachfolgenden Ebene des Baums teilen Sie das Problem in zwei Hälften und erledigen eine konstante Menge zusätzlicher Arbeit.

→ Quasilineare Zeit (O(n log n)) :-

Ein Algorithmus soll in quasilinearer Zeit (auch als log-lineare Zeit bezeichnet) laufen, wenn T (n) = O (n log ^ k n) für eine positive Konstante k; Linearithmische Zeit ist der Fall k = 1.

Beispiel :

Datenstruktur ist eine systematische Methode, Daten zu organisieren, um sie effizient zu nutzen. Die folgenden Begriffe sind die Grundbegriffe einer Datenstruktur.

  • Schnittstelle – Jede Datenstruktur hat eine Schnittstelle. Interface repräsentiert die Menge von Operationen, die eine Datenstruktur unterstützt. Eine Schnittstelle stellt nur die Liste der unterstützten Operationen, die Art der Parameter, die sie akzeptieren können, und den Rückgabetyp dieser Operationen bereit.
  • Implementierung – Implementierung stellt die interne Repräsentation einer Datenstruktur bereit. Die Implementierung bietet auch die Definition der Algorithmen, die bei den Operationen der Datenstruktur verwendet werden.

→ Merkmale einer Datenstruktur :

  • Korrektheit – Die Implementierung der Datenstruktur sollte ihre Schnittstelle korrekt implementieren.
  • Zeitkomplexität – Laufzeit oder die Ausführungszeit von Operationen der Datenstruktur muss so klein wie möglich sein.
  • Speicherkomplexität – Die Speichernutzung einer Datenstrukturoperation sollte so gering wie möglich sein.

→ Bedarf an Datenstruktur:

Da Anwendungen immer komplexer und datenreicher werden, gibt es drei häufige Probleme, mit denen Anwendungen heutzutage konfrontiert sind.

  1. Datensuche – Betrachten Sie ein Inventar von 1 Million (106) Artikeln eines Geschäfts. Wenn die Anwendung ein Element suchen soll, muss sie jedes Mal ein Element in 1 Million (106) Elementen suchen, um die Suche zu verlangsamen. Wenn die Daten wachsen, wird die Suche langsamer.
  2. Prozessorgeschwindigkeit – Die Prozessorgeschwindigkeit ist zwar sehr hoch, aber begrenzt, wenn die Daten auf Milliarden Datensätze anwachsen.
  3. Mehrere Anfragen – Da Tausende von Benutzern gleichzeitig auf einem Webserver nach Daten suchen können, fällt selbst der schnelle Server beim Durchsuchen der Daten aus.

Um die oben genannten Probleme zu lösen, kommen Datenstrukturen zur Rettung. Daten können in einer Datenstruktur so organisiert werden, dass möglicherweise nicht alle Elemente durchsucht werden müssen und die erforderlichen Daten fast sofort durchsucht werden können.

→ Sehen wir uns einen Stack-Wrapper in Swift an:

Wir erstellen einen Wrapper um das Swift-Array, in dem wir das Array als Speicherstruktur verwenden. Arrays geben konstante Zeit (O (1)) Einfügungen und Löschungen, wenn sie vom Ende des Arrays ausgeführt werden.

Es sind FIFO → First In First Out Daten.

Beispiele in iOS : UINavigation Stack, Undo-Funktionalitäten usw.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.