Bonjour ! Je suis enfin de retour après plus de 2 mois sans écrire/toucher du code. J’ai été rattrapé par toute la préparation et la planification du mariage. C’est difficile d’organiser un mariage à l’étranger sans organisateur de mariage. Mais cela en valait la peine puisque notre mariage a été mémorable ! La fièvre du mariage est terminée et il est maintenant temps de me recueillir et de retourner au codage (toujours dans Swift).
Il était difficile de décider ce que je devais réviser en premier avant de commencer à chercher un emploi. Je me suis dit que je devais commencer par les classiques – algorithmes et structures de données, le cœur de la programmation. Dans tout système, à mesure que les données augmentent, les performances ne devraient pas être un problème si le bon algorithme a été utilisé.
Aujourd’hui, j’écris un blog rapide sur 2 types de notations Big O, les algorithmes linéaires et logarithmiques.
Un petit historique sur la notation Big O d’abord.
Analyse asymptotique
L’analyse asymptotique est basée sur des calculs mathématiques qui mesurent essentiellement l’efficacité d’un algorithme lorsque le jeu de données d’entrée augmente (merci Wikipédia !). Il existe d’autres types d’analyse asymptotique selon l’endroit où elle est appliquée, mais en informatique, elle est communément formatée sous la forme de la notation Big O.
Linéaire contre logarithmique
Pour comprendre facilement la notation Big O, nous allons comparer ces deux algorithmes : Linéaire – O(n) et Logarithmique – O(log n).
À titre d’exemple, nous allons essayer de rechercher un nombre dans un tableau trié.
let numberList =
Linéaire O(n) – les performances deviennent moins efficaces lorsque les données augmentent.
Dans la technique linéaire ou « force brute », les performances dépendent de la taille de l’entrée. Pour notre exemple, nous allons lire chaque élément du tableau et chercher le nombre dont nous avons besoin. 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
}
}
}
Bien sûr, cela va fonctionner pour notre petit ensemble de données, mais ce n’est pas très efficace une fois que vous avez des milliers, voire des millions de données.
Logarithmique O(log N) – réduit la recherche en divisant de façon répétée par deux l’ensemble de données jusqu’à ce que vous trouviez la valeur cible.
Utilisation de la recherche binaire – qui est une forme d’algorithme logarithmique, trouve la médiane dans le tableau et la compare à la valeur cible. L’algorithme se déplacera vers le haut ou vers le bas selon que la valeur cible est supérieure, inférieure ou égale à la médiane.
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")
}
}
L’essentiel de cet algorithme se trouve au début, mais il s’aplatit lentement à mesure que nous éliminons la plage non pertinente du tableau et que nous continuons à diviser par deux jusqu’à ce que nous trouvions la valeur cible.
À travers le graphique ci-dessous, nous pouvons facilement comparer comment la plupart des algorithmes ont des performances similaires avec des ensembles de données plus petits, mais diffèrent continuellement lorsque les données augmentent.
Comme vous pouvez le voir, il existe d’autres types de notation Big O dont je parlerai dans les prochains jours. Ciao pour l’instant !