Idées d'analyse d'algorithmes

Cadre d'analyse

1. Utilisez l'échelle d'entrée de l'algorithme n comme paramètre pour analyser l'efficacité de l'algorithme

2. Complexité temporelle : trouvez l'opération de base O(1), puis calculez le nombre de fois qu'elle s'exécute (ignorez la constante de multiplication et concentrez-vous uniquement sur le nombre d'augmentations)

3. Nombre d'augmentations : log2n

4. La pire, la moyenne et la meilleure efficacité font toutes référence à l'efficacité lorsque la taille d'entrée est n (l'efficacité moyenne peut être dérivée de résultats connus)

Cadre principal d'analyse récapitulative :

1. L'efficacité temporelle et l'efficacité spatiale de l'algorithme sont mesurées en fonction de la taille d'entrée.

2. Utilisez le nombre d'exécutions des opérations de base de l'algorithme pour mesurer l'efficacité du temps et utilisez le nombre d'unités supplémentaires consommées par l'algorithme pour mesurer l'unité d'espace

3. Lorsque l'échelle d'entrée est la même, l'efficacité des algorithmes écrits sera significativement différente. Pour ce type d'algorithme, la pire, la moyenne et la meilleure efficacité doivent être analysées

.

4. La principale préoccupation du framework est : son efficacité lorsque l'échelle d'entrée tend à être infinie

Notation asymptotique et types d'efficacité de base

1. O(g(n)) est l'ensemble des fonctions avec des temps de croissance 2. Ω(g(n)) est un ensemble de fonctions avec des temps de croissance >= c*g(n), ordre inférieur

3. θ(g(n)) est un ensemble de fonctions avec des temps de croissance = c*g(n), du même ordre

Vous pouvez utiliser des limites pour comparer le nombre d'augmentations (loi de Lópida)

L’efficacité globale de l’algorithme est déterminée par la partie ayant des temps de croissance plus longs.

Schéma général d'analyse mathématique de problèmes non récursifs

1. Décidez quel paramètre représente la métrique de la taille d'entrée

2. Découvrez les opérations de base de l'algorithme

3. Vérifiez si le nombre d'exécutions des opérations de base dépend uniquement de la taille d'entrée. S'il dépend également d'autres caractéristiques (par exemple : la position de l'élément dans le tableau, etc.), analysez le pire, la moyenne et meilleure efficacité

4. Établir une expression de sommation (éventuellement une expression récursive) du nombre de fois d'exécution de l'opération de base de l'algorithme

5. Utilisez des opérations standards ou des règles d'opérations de sommation pour établir une formule fermée pour le nombre d'opérations, ou au moins déterminer son nombre d'augmentations

Schéma général d'analyse mathématique des problèmes récursifs

1. Décidez quel paramètre représente la métrique de la taille d'entrée

2. Découvrez les opérations de base de l'algorithme

3. Vérifiez si le nombre d'exécutions des opérations de base dépend uniquement de la taille d'entrée. S'il dépend également de certaines autres caractéristiques (par exemple : la position de l'élément dans le tableau, etc.), analysez le pire, la moyenne et meilleure efficacité

4. Pour le nombre de temps d'exécution des opérations de base de l'algorithme, établissez une relation de récursion et les conditions initiales correspondantes.

5. Résolvez cette récurrence, ou au moins déterminez son nombre d'incréments.

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!