Quelles sont les notations Big-O pour les fonctions de tableau PHP courantes ?

Liste des fonctions Big-O pour PHP

Les fonctions de tableau intégrées PHP peuvent varier considérablement dans leur complexité temporelle, et la compréhension de leur Big -O permet d'optimiser les performances du code. Grâce à des benchmarks et à l'analyse de code, une liste complète de Big-O pour diverses fonctions array_* a été compilée :

Lookups

• array_key_exists/isset: O( n) (pratiquement proche de O(1))
• in_array/array_search : O(n)

Fonctions de file d'attente

• array_push : O(∑ var_i, pour tout i)
• array_pop : O (1)
• array_shift : O(n)
• array_unshift : O(n ∑ var_i, pour tout i)

Intersection, Union, Soustraction

• array_intersect_key (intersection à 100 %) : O(Max(param_i_size) * ∑param_i_count, pour tout i)
• array_intersect (100% intersection) : O(n^2 * ∑param_i_count, pour tout i)
• array_intersect_assoc (100% intersection) : O(Max( param_i_size) * ∑param_i_count, pour tout i)
• array_diff: O(π param_i_size, pour tout i)
• array_diff_key: O(∑ param_i_size, pour i != 1)
• array_merge: O(∑ array_i , je != 1)
• • (union) : O(n), où n est la taille du deuxième tableau
• array_replace : O(∑ array_i , pour tous i)

Aléatoire

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

Évident Big-O

• array_fill : O(n)
• array_fill_keys : O(n)
• plage : O(n)
• array_splice : O(longueur de décalage)
• array_slice : O(décalage length) ou O(n) si length = NULL
• array_keys/values/reverse : O(n)
• array_pad : O(pad_size)
• array_flip : O(n )
• array_sum/product/reduce/filter/map/chunk/combine : O(n)

Remarque sur les recherches de tableau

Bien que les recherches de tableau en PHP soient théoriquement O(n), elles se comportent efficacement comme O(1) pour valeurs les plus pratiques. Le benchmarking confirme ce comportement, avec une augmentation de temps d'environ 50 % seulement entre N=1 et N=1 000 000 de recherches.

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!