Quelles sont les complexités temporelles Big-O des fonctions de tableau PHP courantes ?

Big-O pour les fonctions PHP

Lorsque vous travaillez avec PHP, l'efficacité des diverses fonctions intégrées peut varier considérablement. Cet article vise à fournir un aperçu de leurs temps big-O théoriques (ou pratiques).

Lookups

• array_key_exists : O(n), mais fermez efficacement à O(1) en raison des recherches de hachage.
• isset($array[$index]) : O(n), également proche de O(1) en raison des recherches de hachage.
• in_array : O(n), plus lente que les recherches basées sur le hachage.
• array_search : O(n), similaire à in_array.

File d'attente Fonctions

• array_push : O(∑ var_i, pour tout i)
• array_pop : O(1)
• array_shift : O(n), re -indexe les clés.
• array_unshift : O(n ∑ var_i, pour tout i), plus lent en raison de la réindexation.

Array Intersection, Union, Soustraction

• array_intersect_key: O(Max(param_i_size) *∑param_i_count, pour tout i) si l'intersection est 100 %.
• array_intersect : O(n^2*∑param_i_count, pour tout i) si l'intersection est de 100 %.
• array_intersect_assoc : similaire à array_intersect_key.
• array_diff : O(π param_i_size, pour tout i), produit de tous tailles de paramètres.
• array_diff_key: O(∑ param_i_size, for i != 1).

Aléatoire

• shuffle : O(n)
• array_rand : O(n)

Big-O évident

• array_fill : O(n)
• array_fill_keys : O(n)
• plage : O(n)
• array_splice : O(longueur de décalage)
• array_slice : O(longueur de décalage) ou O(n) si la longueur est NULL
• array_keys : O(n)
• array_values : O(n )
• array_reverse : O(n)

Remarque

1. Tous les calculs supposent que les recherches de hachage sont O(1).
2. Les performances asymptotiques peuvent varier en fonction des détails spécifiques de l'implémentation et des données d'entrée.
3. Les tableaux sont de base zéro, donc array_push pousse jusqu'à la fin du tableau.

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!