Cet article vous apporte des connaissances sur la complexité des algorithmes de tables séquentielles en Python. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.
Pour les propriétés temporelles et spatiales de l'algorithme, la chose la plus importante est sa ampleur et sa tendance, donc la fonction pour mesurer sa complexité Le facteur constant peut être ignoré.
La notation Big O est généralement la complexité temporelle asymptotique d'un certain algorithme. La complexité des fonctions de complexité asymptotique couramment utilisées est comparée comme suit :
1 |
|
Un exemple d'introduction de la complexité temporelle, veuillez comparer les deux exemples de code pour voir les résultats du calcul
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 |
|
Comment calculer la complexité temporelle :
1 2 3 4 5 6 |
|
Test de complexité temporelle de la liste
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
|
Résultats de sortie
Complexité des méthodes dans la liste :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Complexité des méthodes dans le dictionnaire (supplémentaire)
1 2 3 4 5 6 7 |
|
Les informations complètes d'une table de séquence comprennent deux parties, une partie est l'ensemble des éléments de la table et l'autre une partie est d'obtenir un fonctionnement correct. Les informations qui doivent être enregistrées comprennent principalement la capacité de la zone de stockage des éléments et le nombre d'éléments dans la table actuelle.
Combinaison d'en-tête et de zone de données : structure intégrée : informations d'en-tête (capacité d'enregistrement et nombre d'éléments existants) et zone de données pour un stockage continu
Structure séparée : les informations d'en-tête et la zone de données ne sont pas stockées en continu, et certaines informations seront utilisées pour stocker des unités d'adresse pour pointer vers la zone de données réelle
Différences et avantages et inconvénients entre les deux :
1 2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1. table (ou une petite table), le système alloue une zone de stockage pouvant contenir 8 éléments
2 Lors d'une opération d'insertion (insertion, ajout), si la zone de stockage de l'élément est pleine, remplacez-la par un stockage. superficie quatre fois plus grande
3. Si la table est déjà très grande (le seuil est de 50 000), changez de politique et adoptez une méthode de doublement. Pour éviter trop d'espace libre.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!