Mesure de la complexité dans les algorithmes utilisant des tableaux auto-initialisés

Question

Lorsqu'il s'agit d'évaluer la complexité temporelle d'un algorithme qui utilise un tableau devant être initialisé, il est généralement exprimé O(k). Où k est la taille du tableau.
Par exemple, le tri de comptage a une complexité temporelle de O(n + k).

Mais que se passe-t-il lorsque le tableau est automatiquement initialisé, comme en Java ou en PHP. Serait-il juste de dire que le comptant le tri (ou tout autre algorithme ayant besoin d'un tableau initialisé) en Java (ou PHP ...) a une complexité temporelle de O(n)?

Answer 1

Parlez-vous de cette http://en.wikipedia.org/wiki/Counting_sort qui a une complexité temporelle de O (n + k)? Vous devez vous rappeler que la complexité temporelle est déterminée pour une machine idéalisée qui n'a pas de caches, de contraintes de ressources et qui est indépendante de la manière dont une machine ou un langage particulier peut réellement fonctionner.

La complexité du temps est encore O(n + k)

Cependant, dans une véritable machine que l'initialisation est susceptible de beaucoup plus efficace que le incrémentées, donc n et k ne sont pas directement comparables. Le modèle pour l'initialisation est comme être séquentiel et très efficace (le n). Si les comptages sont de type int par exemple, la CPU pourrait utiliser long ou des registres de 128 bits pour effectuer l'initialisation.

Le modèle d'accès pour le comptage est susceptible d'être relativement aléatoire et pour les grandes valeurs de k susceptibles d'être beaucoup plus lent. (jusqu'à 10 fois plus lent)

Answer 2

fait ce serait O(n+k)

donc si n est d'un ordre plus élevé que k (beaucoup de doublons dans une sorte de comptage), il peut être mis au rebut dans la complexité du temps ce qui en fait O(n)

Answer 3

L'initialisation automatique n'est pas libre, vous devez toujours le prendre en compte, donc c'est toujours O (n + k).