Hallo! Ich bin endlich wieder da, nachdem ich mehr als 2 Monate keinen Code geschrieben/angefasst habe. Ich wurde von den ganzen Hochzeitsvorbereitungen und -planungen eingeholt. Es ist schwer, eine Hochzeit in Übersee ohne einen Hochzeitsplaner zu organisieren. Aber es hat sich gelohnt, denn unsere Hochzeit war ein echter Knaller! Das Hochzeitsfieber ist vorbei, und jetzt ist es an der Zeit, meine Gedanken zu sammeln und wieder mit dem Programmieren zu beginnen (immer noch in Swift).
Es war schwer zu entscheiden, was ich als Erstes durchgehen sollte, bevor ich mit der Arbeitssuche beginne. Ich dachte mir, ich sollte mit den Klassikern beginnen – Algorithmen und Datenstrukturen, dem Kern der Programmierung. In jedem System sollte die Leistung bei wachsenden Datenmengen kein Problem sein, wenn der richtige Algorithmus verwendet wird.
Heute schreibe ich einen kurzen Blog über 2 Arten von Big O Notationen, lineare und logarithmische Algorithmen.
Zunächst ein paar Hintergrundinformationen zur Big O Notation.
Asymptotische Analyse
Die asymptotische Analyse basiert auf mathematischen Berechnungen, die im Wesentlichen die Effizienz eines Algorithmus bei wachsenden Eingabedaten messen (danke Wikipedia!). Es gibt andere Arten der asymptotischen Analyse, je nachdem, wo sie angewendet wird, aber in der Informatik wird sie üblicherweise als Big O Notation formatiert.
Linear vs. Logarithmisch
Um die Big O Notation leicht zu verstehen, werden wir diese beiden Algorithmen vergleichen: Linear – O(n) und Logarithmisch – O(log n).
Als Beispiel werden wir versuchen, eine Zahl in einem sortierten Array zu suchen.
let numberList =
Linear O(n) – die Leistung wird weniger effizient, wenn die Daten wachsen.
Bei der linearen oder „Brute-Force“-Technik hängt die Leistung von der Eingabegröße ab. In unserem Beispiel lesen wir jedes Element im Array durch und suchen nach der benötigten Zahl. Ganz einfach!
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
Das funktioniert natürlich für unseren kleinen Datensatz, ist aber nicht sehr effizient, wenn man Tausende oder gar Millionen von Daten hat.
Logarithmische O(log N) – grenzt die Suche ein, indem der Datensatz wiederholt halbiert wird, bis der Zielwert gefunden ist.
Binäre Suche – eine Form des logarithmischen Algorithmus – findet den Median im Array und vergleicht ihn mit dem Zielwert. Der Algorithmus bewegt sich entweder nach oben oder nach unten, je nachdem, ob der Zielwert höher, niedriger oder gleich dem Median ist.
func binarySearch(key: Int, iminIndex: Int, imaxIndex: Int) {let midIndex = round(Double(iminIndex + imaxIndex)/2)
let midNumber = numberList
var result = ""//using recursion, we can go up or down the array and reduce the range
if midNumber > key { //target is less than the median so traverse downwards binarySearch(key: key, iminIndex: iminIndex, imaxIndex: Int(midIndex) - 1) } else if midNumber < key { //target is greater than the median so traverse upwards binarySearch(key: key, iminIndex: Int(midIndex) + 1, imaxIndex: imaxIndex) } else if midNumber == key { //Found it!
print("Found it at index \(midIndex)")} else {
print("Value \(key) not found")
}
}
Der größte Teil dieses Algorithmus steht am Anfang, aber er flacht langsam ab, wenn wir den irrelevanten Bereich aus dem Array entfernen und weiter halbieren, bis wir den Zielwert finden.
Anhand des nachstehenden Diagramms können wir leicht vergleichen, wie die meisten Algorithmen bei kleineren Datensätzen eine ähnliche Leistung haben, sich aber bei wachsenden Daten kontinuierlich unterscheiden.
Wie ihr sehen könnt, gibt es noch andere Arten der Big O Notation, die ich in den nächsten Tagen besprechen werde. Ciao für jetzt!