Hejsa! Jeg er endelig tilbage efter mere end 2 måneder uden at skrive/røre ved kode. Jeg blev indhentet af alle bryllupsforberedelserne og planlægningen. Det er svært at gennemføre et bryllup i udlandet uden en bryllupsplanlægger. Men det var det hele værd, da vores bryllup var en for bøgerne! Bryllupsfeberen er ovre, og nu er det tid til at samle mine tanker og komme tilbage til kodning (stadig i Swift).
Det var svært at beslutte, hvad jeg skulle gennemgå først, før jeg begynder at søge job. Jeg tænkte, at jeg skulle starte med klassikerne – algoritmer og datastrukturer, kernen i programmering. I ethvert system, som data vokser, bør ydeevne ikke være et problem, hvis den korrekte algoritme er blevet brugt.
I dag skriver jeg en hurtig blog om 2 typer Big O Notationer, Lineære og Logaritmiske algoritmer.
En lille baggrund om Big O Notation først.
Asymptotisk analyse
Asymptotisk analyse er baseret på matematiske beregninger, der grundlæggende måler effektiviteten af en algoritme, når input datasæt vokser (tak Wikipedia!). Der findes andre typer asymptotisk analyse afhængigt af, hvor den anvendes, men inden for datalogi er den almindeligvis formateret som Big O Notation.
Linear vs. logaritmisk
For nemt at forstå Big O Notation vil vi sammenligne disse to algoritmer: Lineær – O(n) og logaritmisk – O(log n).
Som eksempel vil vi prøve at lede efter et tal i et sorteret array.
let numberList =
Linear O(n) – ydelsen bliver mindre effektiv, når dataene vokser.
I lineær eller “brute force”-teknik afhænger ydelsen af inputstørrelsen. I vores eksempel læser vi hvert element i arrayet igennem og søger efter det nummer, vi har brug for. Easy peasy!
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
Det vil selvfølgelig virke for vores lille datasæt, men det er ikke særlig effektivt, når du har tusindvis eller endda millioner af data.
Logaritmisk O(log N) – indsnævrer søgningen ved gentagne gange at halvere datasættet, indtil du finder målværdien.
Ved binær søgning – som er en form for logaritmisk algoritme, finder du medianen i arrayet og sammenligner den med målværdien. Algoritmen gennemløber enten opad eller nedad afhængigt af, om målværdien er højere end, lavere end eller lig med medianen.
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")
}
}
Den største del af denne algoritme er i begyndelsen, men den flader langsomt ud, efterhånden som vi kasserer det irrelevante område fra arrayet og fortsætter med at halvere, indtil vi finder målværdien.
Gennem nedenstående graf kan vi nemt sammenligne, hvordan de fleste algoritmer har samme ydeevne med mindre datasæt, men løbende adskiller sig fra hinanden, når dataene vokser.
Som du kan se, er der andre typer af Big O Notation, som jeg vil diskutere i de næste dage. Ciao for nu!