DAA - Méthodologie d'analyse

Pour mesurer la consommation de ressources d'un algorithme, différentes stratégies sont utilisées comme indiqué dans ce chapitre.

Analyse asymptotique

Le comportement asymptotique d'une fonction f(n) se réfère à la croissance de f(n) comme n devient grand.

Nous ignorons généralement les petites valeurs de n, puisque nous sommes généralement intéressés à estimer la lenteur du programme sur les gros intrants.

Une bonne règle de base est que plus le taux de croissance asymptotique est lent, meilleur est l'algorithme. Bien que ce ne soit pas toujours vrai.

Par exemple, un algorithme linéaire $ f (n) = d * n + k $ est toujours asymptotiquement meilleur qu'un algorithme quadratique, $ f (n) = cn ^ 2 + q $.

Résolution d'équations de récurrence

Une récurrence est une équation ou une inégalité qui décrit une fonction en fonction de sa valeur sur des entrées plus petites. Les récurrences sont généralement utilisées dans le paradigme diviser pour conquérir.

Considérons T(n) être le temps d'exécution sur un problème de taille n.

Si la taille du problème est suffisamment petite, dites n < c où c est une constante, la solution simple prend un temps constant, qui s'écrit θ(1). Si la division du problème donne un certain nombre de sous-problèmes de taille $ \ frac {n} {b} $.

Pour résoudre le problème, le temps requis est a.T(n/b). Si nous considérons que le temps requis pour la division estD(n) et le temps nécessaire pour combiner les résultats des sous-problèmes est C(n), la relation de récurrence peut être représentée par -

$$ T (n) = \ begin {cas} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) & sinon \ end { cas} $$

Une relation de récurrence peut être résolue en utilisant les méthodes suivantes -

Substitution Method - Dans cette méthode, nous devinons une borne et en utilisant l'induction mathématique nous prouvons que notre hypothèse était correcte.
Recursion Tree Method - Dans cette méthode, un arbre de récurrence est formé où chaque nœud représente le coût.
Master’s Theorem - C'est une autre technique importante pour trouver la complexité d'une relation de récurrence.

Analyse amortie

L'analyse amortie est généralement utilisée pour certains algorithmes où une séquence d'opérations similaires est effectuée.

L'analyse amortie fournit une limite sur le coût réel de la séquence entière, au lieu de limiter le coût de la séquence d'opérations séparément.
L'analyse amortie diffère de l'analyse de cas moyen; la probabilité n'est pas impliquée dans l'analyse amortie. L'analyse amortie garantit la performance moyenne de chaque opération dans le pire des cas.

Ce n'est pas seulement un outil d'analyse, c'est une façon de penser la conception, car la conception et l'analyse sont étroitement liées.

Méthode d'agrégation

La méthode agrégée donne une vue globale d'un problème. Dans cette méthode, sin les opérations prennent le pire des cas T(n)au total. Ensuite, le coût amorti de chaque opération estT(n)/n. Bien que différentes opérations puissent prendre un temps différent, dans cette méthode, le coût variable est négligé.

Méthode comptable

Dans cette méthode, différentes charges sont affectées à différentes opérations en fonction de leur coût réel. Si le coût amorti d'une opération dépasse son coût réel, la différence est affectée à l'objet en tant que crédit. Ce crédit permet de payer les opérations ultérieures pour lesquelles le coût amorti est inférieur au coût réel.

Si le coût réel et le coût amorti de i^th opération sont $ c_ {i} $ et $ \ hat {c_ {l}} $, alors

$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} \ geqslant \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} $$

Méthode potentielle

Cette méthode représente le travail prépayé comme une énergie potentielle, au lieu de considérer le travail prépayé comme un crédit. Cette énergie peut être libérée pour payer les opérations futures.

Si nous exécutons n opérations commençant par une structure de données initiale D₀. Considérons,c_i comme coût réel et D_i comme structure de données de i^thopération. La fonction potentielle Ф correspond à un nombre réel Ф (D_i), le potentiel associé de D_i. Le coût amorti $ \ hat {c_ {l}} $ peut être défini par

$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i}) - \ Phi (D_ {i-1}) $$

Par conséquent, le coût amorti total est

$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limits_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i} ) - \ Phi (D_ {i-1})) = \ Displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) - \ Phi (D_ {0}) $ $

Table dynamique

Si l'espace alloué pour la table n'est pas suffisant, nous devons copier la table dans une table de plus grande taille. De même, si un grand nombre de membres sont effacés de la table, il est judicieux de réallouer la table avec une taille plus petite.

En utilisant l'analyse amortie, nous pouvons montrer que le coût amorti d'insertion et de suppression est constant et que l'espace inutilisé dans une table dynamique ne dépasse jamais une fraction constante de l'espace total.

Dans le prochain chapitre de ce didacticiel, nous aborderons brièvement les notations asymptotiques.