Hallo daar! Ik ben eindelijk terug na meer dan 2 maanden geen code geschreven of aangeraakt te hebben. Ik werd ingehaald door alle voorbereidingen en planning van de bruiloft. Het is moeilijk om een overzeese bruiloft te organiseren zonder een huwelijksplanner. Maar het was het allemaal waard want onze bruiloft was er een voor in de boeken! De bruiloftskoorts is voorbij en nu is het tijd om mijn gedachten te verzetten en weer aan het coderen te gaan (nog steeds in Swift).
Het was moeilijk om te beslissen wat ik als eerste zou herzien voordat ik op banenjacht zou gaan. Ik dacht dat ik moest beginnen met de klassiekers – algoritmen en datastructuren, de kern van programmeren. In elk systeem, als data groeit, zou performance geen probleem moeten zijn als het juiste algoritme is gebruikt.
Vandaag schrijf ik een snelle blog over 2 soorten Big O Notaties, Lineaire en Logaritmische algoritmen.
Een beetje achtergrond over Big O Notatie eerst.
Asymptotische Analyse
Asymptotische analyse is gebaseerd op wiskundige berekeningen die in principe meet de efficiëntie van een algoritme als input dataset groeit (bedankt Wikipedia!). Er zijn andere soorten asymptotische analyse, afhankelijk van waar het wordt toegepast, maar in de informatica, is het meestal geformatteerd als Big O Notation.
Lineair vs. Logaritmisch
Om Big O Notation gemakkelijk te begrijpen, zullen we deze twee algoritmen vergelijken: Lineair – O(n) en Logaritmisch – O(log n).
Als voorbeeld zullen we proberen een getal te zoeken in een gesorteerde array.
let numberList =
Lineair O(n) – de prestaties worden minder efficiënt naarmate de gegevens groeien.
In de Lineaire of “brute kracht” techniek, is de prestatie afhankelijk van de invoergrootte. In ons voorbeeld lezen we elk item in de array en zoeken naar het nummer dat we nodig hebben. Makkelijk zat!
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
Natuurlijk werkt dat voor onze kleine dataset, maar het is niet erg efficiënt als je duizenden, zelfs miljoenen gegevens hebt.
Logaritmisch O(log N) – verkleint de zoekactie door de dataset herhaaldelijk te halveren tot je de doelwaarde vindt.
Door binair zoeken – een vorm van logaritmisch algoritme, wordt de mediaan in de matrix gevonden en vergeleken met de doelwaarde. Het algoritme zal naar boven of naar beneden gaan, afhankelijk van of de doelwaarde hoger dan, lager dan of gelijk aan de mediaan is.
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")
}
}
Het grootste deel van dit algoritme is aan het begin, maar het wordt langzaam vlakker naarmate we het irrelevante bereik uit de matrix verwijderen en blijven halveren tot we de doelwaarde vinden.
Door middel van onderstaande grafiek kunnen we gemakkelijk vergelijken hoe de meeste algoritmen vergelijkbare prestaties leveren bij kleinere datasets, maar voortdurend verschillen naarmate de gegevens groeien.
Zoals u ziet zijn er nog meer soorten Big O Notation die ik de komende dagen zal bespreken. Ciao voor nu!