Ciao! Sono finalmente tornato dopo più di 2 mesi senza scrivere/toccare codice. Sono stato preso da tutti i preparativi e dall’organizzazione del matrimonio. È difficile organizzare un matrimonio all’estero senza un wedding planner. Ma ne è valsa la pena dato che il nostro matrimonio è stato uno di quelli da ricordare! La febbre del matrimonio è finita e ora è tempo di raccogliere i miei pensieri e tornare a codificare (ancora in Swift).
È stato difficile decidere cosa rivedere prima di iniziare la ricerca di lavoro. Ho pensato che dovrei iniziare con i classici – algoritmi e strutture dati, il nucleo della programmazione. In qualsiasi sistema, quando i dati crescono, le prestazioni non dovrebbero essere un problema se è stato usato l’algoritmo corretto.
Oggi, sto scrivendo un blog veloce su 2 tipi di notazioni Big O, algoritmi lineari e logaritmici.
Prima un po’ di background sulla notazione Big O.
Analisi asintotica
L’analisi asintotica è basata su calcoli matematici che fondamentalmente misura l’efficienza di un algoritmo al crescere del dataset di input (grazie Wikipedia!). Ci sono altri tipi di analisi asintotica a seconda di dove viene applicata, ma in Informatica, è comunemente formattata come Big O Notation.
Linear vs. Logarithmic
Per capire facilmente Big O Notation, confronteremo questi due algoritmi: Lineare – O(n) e Logaritmico – O(log n).
Come esempio, proveremo a cercare un numero in un array ordinato.
let numberList =
Lineare O(n) – la performance diventa meno efficiente al crescere dei dati.
Nella tecnica Lineare o “forza bruta”, la performance dipende dalla dimensione dell’input. Per il nostro esempio, leggeremo ogni elemento dell’array e cercheremo il numero che ci serve. 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
}
}
}
Ovviamente questo funzionerà per il nostro piccolo set di dati, ma non è molto efficiente quando si hanno migliaia, anche milioni di dati.
Logaritmico O(log N) – restringe la ricerca dimezzando ripetutamente il set di dati fino a trovare il valore target.
Utilizzando la ricerca binaria – che è una forma di algoritmo logaritmico, trova la mediana nell’array e la confronta con il valore target. L’algoritmo si sposta verso l’alto o verso il basso a seconda che il valore target sia superiore, inferiore o uguale alla 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")
}
}
Il grosso di questo algoritmo è all’inizio, ma si appiattisce lentamente man mano che scartiamo l’intervallo irrilevante dalla matrice e continuiamo a dimezzare fino a trovare il valore target.
Attraverso il grafico qui sotto, possiamo facilmente confrontare come la maggior parte degli algoritmi hanno prestazioni simili con set di dati più piccoli, ma differiscono continuamente al crescere dei dati.
Come puoi vedere ci sono altri tipi di Big O Notation che discuterò nei prossimi giorni. Ciao per ora!