Plus rapide que l'implémentation O (log N) int set en Java?

-2

Fastutil a une belle classe IntAVLTreeSet qui a la méthode #firstInt() et #lastInt(), que j'ai besoin.Plus rapide que l'implémentation O (log N) int set en Java?

Malheureusement, AVL Tree est O (log N).

Y a-t-il O (1) implémentations de cela? Est-ce possible?

MISE À JOUR

Je veux O (1) lookups. Trouver des marges peut être plus lent.

Source

2017-04-21 Dims

Cherchez-vous mieux que O (logN) insérer et O (1) firstInt() ou insérer l'heure constante? –

Avez-vous besoin d'un arbre avl ou est-ce que n'importe quel type de structure de données le fera? Vous pouvez obtenir une recherche min à temps constant avec une pile – Joni

Parlez-vous de 'O (1)' pour 'lastInt()' ou quoi? Dire "Arbre AVL est O (log N)" est très peu clair, puisque la complexité est dans les opérations et non dans les structures de données elles-mêmes. – Kayaman

La classe que vous mentionnez: selon its source code, firstInt() et lastInt() sont déjà O(1). La classe met en cache les première et dernière entrées de l'arborescence.

Si vous souhaitez qu'une recherche plus générale de n'importe quelle clé soit O(1), vous aurez besoin d'une structure de données différente.

Source

2017-04-21 14:36:45 JeremyP

Plus rapide que l'implémentation O (log N) int set en Java?

Répondre

Questions connexes