Bună ziua! Am revenit în sfârșit după mai bine de 2 luni în care nu am scris/atingut cod. Am fost prins cu toată pregătirea și planificarea nunții. Este greu să faci o nuntă în străinătate fără un planificator de nunți. Dar totul a meritat, deoarece nunta noastră a fost una pentru cărți! Febra nunții a trecut și acum este timpul să-mi adun gândurile și să mă întorc la codare (tot în Swift).
A fost greu să mă decid ce să revizuiesc mai întâi înainte de a începe căutarea unui loc de muncă. M-am gândit că ar trebui să încep cu clasicii – algoritmi și structuri de date, nucleul programării. În orice sistem, pe măsură ce datele cresc, performanța nu ar trebui să fie o problemă dacă a fost folosit algoritmul corect.
Astăzi, scriu un blog rapid despre 2 tipuri de notații Big O, algoritmii liniari și logaritmici.
În primul rând, un mic istoric despre Notația Big O.
Analiza asimptotică
Analiza asimptotică se bazează pe calcule matematice care, practic, măsoară eficiența unui algoritm pe măsură ce crește setul de date de intrare (mulțumesc Wikipedia!). Există și alte tipuri de analiză asimptotică, în funcție de locul în care este aplicată, dar în informatică, este în mod obișnuit formatată ca Big O Notation.
Linear vs. Logaritmic
Pentru a înțelege mai ușor Big O Notation, vom compara acești doi algoritmi: Linear – O(n) și Logaritmic – O(log n).
Ca exemplu, vom încerca să căutăm un număr într-un tablou sortat.
let numberList =
Linear O(n) – performanța devine mai puțin eficientă pe măsură ce datele cresc.
În tehnica Linear sau „brute force”, performanța depinde de mărimea datelor de intrare. Pentru exemplul nostru, vom citi fiecare element din matrice și vom căuta numărul de care avem nevoie. 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
}
}
}
Desigur că acest lucru va funcționa pentru setul nostru de date mic, dar nu este foarte eficient odată ce aveți mii, chiar milioane de date.
Logaritmic O(log N) – restrânge căutarea prin înjumătățirea repetată a setului de date până când găsiți valoarea țintă.
Utilizarea căutării binare – care este o formă a algoritmului logaritmic, găsește mediana din matrice și o compară cu valoarea țintă. Algoritmul va parcurge fie în sus, fie în jos, în funcție de faptul că valoarea țintă este mai mare, mai mică sau egală cu mediana.
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")
}
}
Principalul acestui algoritm se află la început, dar se aplatizează încet pe măsură ce eliminăm intervalul irelevant din matrice și continuăm să înjumătățim până când găsim valoarea țintă.
Cu ajutorul graficului de mai jos, putem compara cu ușurință modul în care majoritatea algoritmilor au performanțe similare cu seturi de date mai mici, dar diferă continuu pe măsură ce datele cresc.
După cum puteți vedea, există și alte tipuri de notație Big O pe care le voi discuta în zilele următoare. Ciao deocamdată!
.