Hej! Jag är äntligen tillbaka efter mer än 2 månader utan att skriva/röra kod. Jag fastnade i alla bröllopsförberedelser och planering. Det är svårt att genomföra ett bröllop utomlands utan en bröllopsplanerare. Men det var värt det eftersom vårt bröllop var en riktig höjdare! Bröllopsfebern är över och nu är det dags att samla mina tankar och återgå till kodning (fortfarande i Swift).
Det var svårt att bestämma sig för vad jag ska granska först innan jag börjar söka jobb. Jag tänkte att jag skulle börja med klassikerna – algoritmer och datastrukturer, kärnan i programmering. I alla system, när data växer, bör prestanda inte vara ett problem om rätt algoritm har använts.
I dag skriver jag en snabb blogg om 2 typer av Big O-notationer, linjära och logaritmiska algoritmer.
En liten bakgrund om Big O Notation först.
Asymptotisk analys
Asymptotisk analys är baserad på matematiska beräkningar som i princip mäter effektiviteten hos en algoritm när inmatningsdatamängden växer (tack Wikipedia!). Det finns andra typer av asymptotisk analys beroende på var den tillämpas, men inom datavetenskap är den vanligen formaterad som Big O-notation.
Linjär vs. logaritmisk
För att lätt förstå Big O-notation jämför vi dessa två algoritmer: Linjär – O(n) och logaritmisk – O(log n).
Som exempel försöker vi leta efter ett nummer i en sorterad matris.
let numberList =
Linjär O(n) – prestandan blir mindre effektiv när datan växer.
I den linjära tekniken, som kallas ”brute force”-tekniken, är prestandan beroende av storleken på indata. I vårt exempel läser vi igenom varje objekt i matrisen och söker efter det nummer vi behöver. Lätt som en plätt!
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
Självklart kommer det att fungera för vårt lilla dataset, men det är inte särskilt effektivt när du har tusentals, till och med miljontals data.
Logaritmisk O(log N) – begränsar sökningen genom att upprepade gånger halvera datamängden tills du hittar målvärdet.
Användning av binär sökning – som är en form av logaritmisk algoritm, hittar medianen i matrisen och jämför den med målvärdet. Algoritmen går antingen uppåt eller nedåt beroende på om målvärdet är högre än, lägre än eller lika 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örsta delen av denna algoritm finns i början, men den planar långsamt ut när vi utesluter det irrelevanta intervallet från matrisen och fortsätter att halvera tills vi hittar målvärdet.
Med hjälp av grafen nedan kan vi enkelt jämföra hur de flesta algoritmer har liknande prestanda med mindre datamängder men kontinuerligt skiljer sig åt när data växer.
Som ni kan se finns det andra typer av Big O-notation som jag kommer att diskutera under de kommande dagarna. Ciao tills vidare!