Exigences : Vous devez définir un type de collection en lecture seule, qui n’ajoutera pas, ne supprimera ni ne modifiera pas la collection, mais ne fera qu’interroger la collection. Nous espéronsPlus la requête est rapide, mieux c’est。
Comparaisons d’ensembles courantes
Lorsqu’on décrit la complexité de l’algorithme, o(1), o(n), o(logn), o(logn), o(nlogn) sont couramment utilisés pour exprimer la complexité temporelle de l’algorithme correspondant, qui est l’expression de la complexité spatiotemporelle de l’algorithme. Il est utilisé non seulement pour représenter la complexité temporelle, mais aussi pour représenter la complexité spatiale.
O est suivi d’une fonction entre parenthèses qui indique la relation entre le temps/l’espace consommé par un algorithme et la quantité de données produites. où n représente la quantité de données d’entrée.
Par exemple, si la complexité temporelle est O(n), cela signifie que la quantité de données augmente plusieurs fois, et que la consommation de temps augmente également plusieurs fois. Par exemple, les algorithmes de déplacement courants. Un autre exemple est la complexité temporelle O(n^2), ce qui signifie que lorsque le volume de données augmente n fois, il faut du temps pour augmenter n fois carrés, ce qui est une complexité temporelle plus élevée que linéaire. Par exemple, le tri par bulles est un algorithme typique de O(n^2), qui doit être balayé n × n fois pour trier n nombres.
Un autre exemple est O(logn), lorsque les données augmentent n fois, il faut du temps pour augmenter les logn (le log ici est basé sur 2, par exemple, lorsque les données sont multipliées par 256, le temps requis n’augmente que de 8 fois, ce qui est inférieur à celui linéaire). La recherche binaire est l’algorithme de O (logn), qui élimine la moitié des possibilités à chaque fois qu’elle est trouvée, et la recherche dans 256 données n’a besoin d’être trouvée que 8 fois pour trouver la cible.
O(nlogn) est le même, c’est-à-dire n multiplié par logn, lorsque les données sont multipliées par 256, la consommation de temps augmente de 256 * 8 = 2048 fois. Cette complexité est supérieure à la linéarité sous le carré. Fusionner et trier correspond à la complexité temporelle de O(nlogn).
O(1) est la complexité spatiotemporelle la plus faible, c’est-à-dire que le temps/espace consommé est indépendant de la taille des données d’entrée ; peu importe combien de fois les données d’entrée sont augmentées, le temps/espace consommé reste inchangé. L’algorithme de hachage est une complexité temporelle typique O(1), qui peut trouver la cible après un seul calcul (quels que soient les conflits), quelle que soit la taille des données.
Cet article utilise la paire BenchmarkDotNetList、HashSet、SortedSet、DictionaryPour une requête en benchmarking, référez-vous aux points suivants :
Le code est le suivant :
Résultat du test : Trouver une clé sur un dictionnaire ou un ensemble de hachage est bien plus rapide que de chercher dans une liste et un ensemble trié. La complexité temporelle des algorithmes Dictionary et HashSet est O(1), et pour économiser de la mémoire, la valeur du dictionnaire ne nous sert à rien, j’ai donc tout de même choisi le stockage HashSet.
|
Publié sur 07/03/2022 16:47:50
|
|
|
|
Publié sur 07/03/2022 23:09:48
|
Propriétaire|
Publié sur 09/03/2022 09:55:12
|
