J'essaie de mettre en œuvre un algorithme de balayage d'avion et pour cela, j'ai besoin de connaître la complexité temporelle de JAVA.UTIL.HASHMAP Class 'Keyset () Méthode. Je soupçonne que c'est O (n log n). Suis-je correct?
5 Réponses :
Ceci devrait être faisable dans O (n) Temps ... Une carte de hachage est généralement implémentée sous forme de grand réseau de seau, la taille du godet est (généralement) directement proportionnelle à la taille de la carte de hachage. Pour récupérer le jeu de clé, le godet doit être itéré à travers et pour chaque élément de jeu, la clé doit être extraite (via une collection intermédiaire ou un itérateur avec un accès direct au godet) ...
** Modifier: Comme d'autres ont souligné, la méthode du Keyset réelle () s'exécutera dans O (1) Temps, toutefois, itérant sur le Keyset ou le transférer à une collection dédiée sera une opération O (N). Pas tout à fait sûr lequel vous recherchez **
O (n) n'est pas complètement précis, par Ma réponse (la complexité temporelle de l'itération dépend de la taille de la carte ainsi que de sa capacité, bien que la pièce de capacité ne puisse pas modifier la complexité du temps d'itération, à moins que la carte soit mal configurée pour ses données).
@ M.Justin - et par ma réponse ... à partir de 9 mois plus tôt.
Ce serait sûrement O (1). Tout ce qu'il fait est de retourner un objet wrapper sur le hashmap.
Si vous parlez de marcher sur le Keyset, c'est O (n), puisque chaque appel suivant () est O (1), et cela doit être effectué n Times.
O (n) n'est pas complètement précis, par Ma réponse (la complexité temporelle de l'itération dépend de la taille de la carte ainsi que de sa capacité, bien que la pièce de capacité ne puisse pas modifier la complexité du temps d'itération, à moins que la carte soit mal configurée pour ses données).
Les collections Java ont beaucoup d'espace et ne prennent donc pas beaucoup de temps. Cette méthode est, je crois, o (1). La collection est juste assis là.
Obtenir le KEYSET est Le fichier ... itération à travers le fichier En réalité, ce n'est pas toujours vrai:
Il est vrai pour un c'est faux si le Il y a une clause d'évacuation cependant. Étant donné que D'autre part, O (1) et pas cher. Ceci est parce que hashmap.keyset () renvoie le keyset correspondant associé au hashmap .
retourné est pas une copie des touches, mais une enveloppe pour l'état hashmap . En effet, si vous mettez à jour le jeu, vous pouvez effectivement modifier l'état de HASHMAP ; par exemple. Calling Clear () sur l'ensemble Effacera le HASHMAP !
renvoyé prendra évidemment O (n) heure.
hashmap est créé à l'aide de nouveau hashmap <> () . Le pire des cas est d'avoir tous les clés N dans la même chaîne de hachage. Toutefois, si la carte est devenue naturellement, il y aura toujours N entrées et O (n) emplacements dans la matrice de hachage. Ainsi itération de l'ensemble d'entrée impliquera des opérations O (n) .
hashmap est créé avec nouveau hashmap <> (capacité) et un mauvais mauvais (trop grand) capacité Estimation. Ensuite, il faudra O (cap) + O (n) Opérations pour itérer le jeu d'inscription. Si nous traitons Cap en tant que variable, c'est O (max (cap, n)) , qui pourrait être pire que O (n) .
capacité est un int dans l'API hadrmap , la limite supérieure de CAP est 2 31 . Donc, pour vraiment valeurs de Cap et n , la complexité est o (n) .
n est limité par la quantité de mémoire disponible et dans la pratique, vous avez besoin d'un tas dans l'ordre de 2 38 octets (256 Go) pour < code> n pour dépasser la valeur la plus importante la valeur . Et pour une carte de taille, vous seriez mieux à l'aide d'une mise en œuvre de hashtable réglées pour d'énormes cartes. Ou n'utilisant pas une estimation excessivement de grande capacité!
(Remarque: la 2e partie de cette réponse était à l'origine une réponse distincte.)
Pour résoudre le "itérateur à travers l'ensemble renvoyé prendra évidemment O (n) le commentaire", ce n'est pas vraiment correct par the DOC Commentaires de L'itération sur les vues de collecte nécessite du temps proportionnel à la "capacité" de l'instance HASHMAP (nombre de godets) plus sa taille (nombre de mappages de valeur de clé). Ainsi, il est très important de ne pas définir la capacité initiale trop élevée (ou le facteur de charge trop bas) si la performance d'itération est importante.
donc en d'autres termes, itération sur le fichier renvoyé prendra HashMap :
o (n + c) où n est la taille de la carte de la carte et c est sa capacité, pas O (n) . Si une capacité initiale ou un facteur de charge initial de taille inappropriée a été choisie, la valeur de C pourrait surgir la taille réelle de la carte en termes de temps d'itération.
Dupliquer la réponse. Dit ce que j'ai écrit il y a 9 mois.
@Stephenc, je vais prendre votre parole pour cela, car il semble que vous ayez supprimé cette réponse et la fusionnée dans votre autre, et je n'ai pas assez de réputation pour voir des réponses supprimées. Je dois avoir manqué votre réponse en adressant ce point.
Je ne pense pas marcher à travers l'ensemble prend "évidemment" o (n) heure. L'ensemble peut ne pas être réellement généré. C'est peut-être juste un objet qui peut être utilisé pour itérer. Et, quel est le n ici? Les articles ou les godets?
Ici N est le nombre d'entrées dans le hashmap. Si l'ensemble a n elelements, itérer sur l'ensemble des éléments N, la complexité de temps sera O (n).