J'ai un tableau non trié . J'ai des requêtes dans lesquelles je donne une plage, puis la valeur maximale de cette plage doit être retournée. Par exemple:
array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78
Quel algorithme ou structure de données dois-je construire pour récupérer rapidement la valeur maximale de n'importe quelle plage. (Il y a beaucoup de requêtes)
EDIT: Ceci est en effet une version simple du problème réel. Je peux avoir la taille du tableau jusqu'à 100 000 et le nombre de requêtes jusqu'à 100 000. J'ai donc certainement besoin d'un prétraitement qui facilitera une réponse rapide aux requêtes.
algorithms
array
sudeepdino008
la source
la source
Réponses:
Je pense que vous pourriez construire une sorte d'arbre binaire où chaque nœud représente la valeur maximale de ses enfants:
Ensuite, il vous suffit de trouver un moyen de déterminer les nœuds que vous devez vérifier au minimum pour trouver la valeur maximale dans la plage interrogée. Dans cet exemple, pour obtenir la valeur maximale dans la plage d'index
[2, 6]
(incluse) que vous auriez à lamax(45, 78, 4)
place demax(9, 45, 78, 2, 4)
. À mesure que l'arbre grandit, le gain augmente.la source
78
(et ignorer le2
), car pour autant qu'elle sache, l'index se6
trouve dans ce sous-arbre.Pour compléter la réponse de ngoaho91.
La meilleure façon de résoudre ce problème est d'utiliser la structure de données de l'arborescence des segments. Cela vous permet de répondre à de telles requêtes dans O (log (n)), ce qui signifierait que la complexité totale de votre algorithme serait O (Q logn) où Q est le nombre de requêtes. Si vous utilisiez l'algorithme naïf, la complexité totale serait O (Q n) qui est évidemment plus lente.
Il y a cependant un inconvénient à l'utilisation des arbres de segments. Cela prend beaucoup de mémoire, mais souvent vous vous souciez moins de la mémoire que de la vitesse.
Je décrirai brièvement les algorithmes utilisés par ce DS:
L'arbre de segment n'est qu'un cas particulier d'un arbre de recherche binaire, où chaque nœud contient la valeur de la plage à laquelle il est affecté. Le nœud racine se voit attribuer la plage [0, n]. L'enfant gauche se voit attribuer la plage [0, (0 + n) / 2] et l'enfant droit [(0 + n) / 2 + 1, n]. De cette façon, l'arbre sera construit.
Créer un arbre :
Arbre de requête
Si vous avez besoin de plus d'explications, faites le moi savoir.
BTW, Segment Tree prend également en charge la mise à jour d'un seul élément ou d'une plage d'éléments dans O (log n)
la source
O(log(n))
que chaque élément soit ajouté à l'arborescence. Par conséquent, la complexité totale estO(nlog(n))
Le meilleur algorithme serait en temps O (n) comme ci-dessous, commençons, fin soit l'indice des limites de la plage
la source
max
poura[i]
et démarrer lafor
boucle ài+1
.)start
, s'arrêter àend
). Et je suis d'accord, c'est le meilleur pour une recherche unique. La réponse de @ ThijsvanDien n'est meilleure que si la recherche doit se produire plusieurs fois, car elle prend plus de temps à configurer initialement.Les solutions d'arbre binaire / segment d'arbre pointent en effet dans la bonne direction. On pourrait cependant objecter qu'ils nécessitent beaucoup de mémoire supplémentaire. Il existe deux solutions à ces problèmes:
Le premier point est que parce que l'arbre est très structuré, vous pouvez utiliser une structure semblable à un tas pour définir implicitement l'arbre plutôt que de représenter l'arbre avec des nœuds, des pointeurs gauche et droit, des intervalles, etc. Cela économise beaucoup de mémoire avec essentiellement aucun impact sur les performances - vous devez effectuer un peu plus d'arithmétique de pointeur.
Le deuxième point est que, au prix d'un peu plus de travail pendant l'évaluation, vous pouvez utiliser un arbre M-aire plutôt qu'un arbre binaire. Par exemple, si vous utilisez un arbre à 3 aires, vous calculerez le maximum de 3 éléments à la fois, puis 9 éléments à la fois, puis 27, etc. Le stockage supplémentaire requis est alors N / (M-1) - vous pouvez prouver en utilisant la formule de la série géométrique. Si vous choisissez M = 11, par exemple, vous aurez besoin de 1 / 10ème du stockage de la méthode de l'arbre binaire.
Vous pouvez vérifier que ces implémentations naïves et optimisées en Python donnent les mêmes résultats:
contre.
la source
essayez la structure de données "arbre de segment"
il y a 2 étapes
build_tree () O (n)
requête (int min, int max) O (nlogn)
http://en.wikipedia.org/wiki/Segment_tree
Éditer:
vous ne lisez pas le wiki que j'ai envoyé!
cet algorithme est:
- vous traversez le tableau 1 fois pour construire l'arborescence. O (n)
- 100000000+ fois où vous voulez connaître le maximum de n'importe quelle partie du tableau, appelez simplement la fonction de requête. O (logn) pour chaque requête
- implémentez c ++ ici geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ l'
ancien algorithme est:
chaque requête, il suffit de parcourir la zone sélectionnée et de trouver.
donc, si vous allez utiliser cet algorithme pour traiter une fois, OK, il est plus lent que l'ancienne. mais si tu vas traiter grand nombre de requêtes (milliards), il est très efficace , vous pouvez générer un fichier texte comme celui - ci, pour le test en
ligne 1: 50000 nombre aléatoire 0-1000000, divisé par « (espace) » (c'est le tableau) en
ligne 2: 2 nombre aléatoire de 1 à 50000, divisé par '(espace)' (c'est la requête)
...
ligne 200000: aime la ligne 2, c'est aussi la requête aléatoire
c'est l'exemple du problème, désolé mais c'est en vietnamien
http://vn.spoj.com/problems/NKLINEUP/
si vous le résolvez à l'ancienne, vous ne passez jamais.
la source
O(n)
recherche dans le tableau, comme décrit dans la réponse de tarun_telang. Le premier instinct est queO(log n + k)
c'est plus rapide queO(n)
, maisO(log n + k)
c'est juste la récupération du sous-tableau - équivalent à l'O(1)
accès au tableau étant donné les points de début et de fin. Vous auriez encore besoin de le parcourir pour trouver le maximum.Vous pouvez obtenir O (1) par requête (avec une construction O (n log n)) à l'aide d'une structure de données appelée table clairsemée. Pour chaque puissance de 2, économisons le maximum pour chaque segment de cette longueur. Maintenant, étant donné le segment [l, r), vous obtenez un maximum de maximum sur [l + 2 ^ k) et [r-2 ^ k, r) pour k approprié. Ils se chevauchent mais c'est OK
la source