Si nous avons deux matrices de taille N chacune et que nous voulons trier leurs sommes, l'approche naïve serait de stocker leurs sommes dans l'espace O (n ^ 2) et de le trier dans le temps O (n ^ 2 logn). Supposons que nous ayons le même temps d'exécution de O (n ^ 2 logn), comment stockerions-nous les sommes dans l'espace linéaire de O (n)?
Je suppose que nous n'avons pas l'intention de stocker toutes les sommes puisqu'ils n ^ 2 éléments ne vont pas entrer dans n espace et que nous imprimons simplement tout dans l'ordre trié, cela signifie donc que nous devons dynamiquement stocker les articles? Des conseils?
(Ceci est un problème de devoirs)
3 Réponses :
Le problème, si je comprends bien, c'est que nous voulons trouver les sommes et les imprimer dans la commande triée.
La restriction consiste à utiliser uniquement une mémoire O (n) et O (n ^ 2 journal n) dans le processus. Considérez la table ci-dessus comme Pour concevoir cela, réfléchissez à la manière de fusionner deux listes triées (comme dans Mergesort), puis de trois listes, etc. au.
Ceci étend de manière trivialement la fusion n listes (lignes) de n éléments chacun.
Si nous trions les matrices initiales de sorte que a1 <= a2 <= ... <= ... <= un et b1 <= b2 <= ... <= bn , chaque liste est déjà trié.
Maintenant, le problème est réduit à la fusion de N Listes triées. n listes de longueur n toutes les opérations pour chaque élément de sortie, pour un total de O (n ^ 3) .
Ce qui reste, c'est de réduire le temps d'obtenir chaque élément de sortie jusqu'à O (journal n) .
Comme vous demandez un indice, mais pas une solution complète, voir si vous pouvez gérer cette étape vous-même.
Vous mentionnez que vous souhaitez fusionner n listes de tri. Comment fusionnerions-nous toutes ces listes dans n espace s'il y a des listes occupant plus que n espace?
@Maregor Une liste n'est pas stockée explicitement. Au lieu de cela, nous stockons simplement un pointeur sur l'endroit où nous avons cessé de traverser cette liste. Par exemple, si nous voulons maintenant le 4ème élément de la 9ème liste, nous savons que c'est A9 + B4 . Si nous choisissons de consommer (sortie) cet élément, le pointeur de cette liste se déplace à sa 5ème valeur, A9 + B5 . Le pointeur est juste un numéro de 1 à n + 1 , la dernière signification de la liste est déjà épuisée.
Donc, le temps de tri des deux tableaux est juste o (nlogn) + o (nlogn) non?
@Maregor Ouais, comme ils sont tous les deux la taille n , et nous les trions indépendamment.
@Palcente qui dépend de Stratégie de sélection de pivot .
QuickSort court à O (n LG N) en moyenne et o (n ^ 2) dans le pire des cas (si les matrices sont déjà triées) ...
Une fois que les deux tableaux sont triés, je pensais avoir un pointeur à chaque matrice pour additionner les sommes et les imprimer, mais cela ne fonctionne pas bien et que l'espace O (n) ne peut pas être utilisé. Devrais-je simplement stocker la première liste dans l'espace O (n) et comparer d'autres listes possibles?
@Maregor Je ne sais pas comment faire cela avec deux pointeurs seulement. Imaginez n = 10 et les pointeurs sont à (5, 5) , pointant ainsi à la somme A5 + B5 . Comment trouvez-vous ce qui est ensuite? Il peut bien être a4 + b7 , A1 + b6 ou A6 + B2 . Cela dit, je ne prétends pas qu'une telle solution est impossible, je ne le vois tout simplement pas.
C'est vrai, alors c'est une mauvaise idée. Mais comment utiliser n espace le faire fonctionner?
@Maregor pour chaque ligne i , nous nous souvenons j pointant à la somme ai + bj nous nous sommes arrêtés.
dans Python, vous pouvez quelque chose comme ça:
5 6 6 7 7 7 8 8 9
Wow, c'est une courte mise en œuvre! Python brille vraiment ici.
Pourriez-vous expliquer pour V dans heapq.merge (* carte (ajouter, a)):? Je ne suis pas vraiment bon à Python et je pourrais utiliser certaines explications.
[add_to_b (x) pour x dans a] créera un générateur pour chaque x appartenant à A . Le générateur ajoute x à chaque élément de B . Nous passons cette séquence de générateurs à HEAPQ.MERGE qui les fusionnera.
L'add_to_b ajoute tous les éléments V en B, mais vous passez tous les éléments de l'entre eux. Comment puis-je visualiser ce qui se passe là-bas?
Si a = [1, 2, 3] , b = [4, 5, 6] alors add_to_b (1) générera 1 + 4, 1 + 5, 1 + 6 , add_to_b (2) générera 2 + 4, 2 + 5, 2 + 6 , < Code> add_to_b (3) générera 3 + 4, 3 + 5, 3 + 6 . Donc nous avons 3 séquences a) 5, 6, 7 b) 6, 7, 8 c) 7, 8, 9 qui nécessite être fusionné.
Trier d'abord les 2 tableaux en ordre croissant, la complexité de l'heure est Comment maintenir le minimum N SUMS? Premier push puis les n éléments du tas sont les plus petites sommes les plus petites. La complexité de temps est 2 * O (n * lgn) , qui peut également être considéré comme O (n * lgn) . Ensuite, utilisez un n + 1 pour maintenir les Numes n minimales. a1 + b1 , A1 + b2 , A1 + b3 , ..., A1 + bn à le tas. Alors pour chaque a [i], 1 <= i b [j], 0 <= j , appuyez sur A [I] + b [j] puis pop le plus grand: O (n ^ 2 * lgn) , la complexité de l'espace est o (n) .
Que voulez-vous dire exactement par "somme de deux tableaux"? Veuillez fournir un exemple avec la sortie attendue et ce que vous avez essayé jusqu'à présent.
Si nous avons 1 2 3 4 5 et 2 3 4 5 6, les sommes seraient alors 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 6 7 8 9 10 7 8 9 10 11.