J'ai une affectation à écrire un algorithme (pas dans une langue particulière, juste pseudo-code) qui reçoit une matrice [taille: m x n] triée de manière à ce que toutes ses lignes soient triées et toutes les lignes Ses colonnes sont triées individuellement et trouve une certaine valeur dans cette matrice. Je dois écrire l'algorithme le plus efficace que je puisse penser.
La matrice ressemble à quelque chose comme: mon idée est de commencer à la première rangée et au dernier rang colonne et simplement vérifier la valeur, si elle est plus grande baisser et si elle est plus petite que d'aller à gauche et continuez à le faire jusqu'à ce que la valeur soit trouvée ou jusqu'à ce que les index soient hors limites (au cas où la valeur n'existe pas). Cet algorithme fonctionne à la complexité linéaire O (M + N). On m'a dit qu'il était possible de le faire avec une complexité logarithmique. Est-il possible? et si oui, comment?
9 Réponses :
Et c'est comme ça que l'exemple d'entrée a l'air? Tri par des diagonales? C'est un genre intéressant, sûr d'être sûr.
Étant donné que la ligne suivante peut avoir une valeur inférieure à celle de toute valeur de cette ligne, vous ne pouvez rien assumer notamment sur une rangée de données donnée. p>
Je voudrais (si vous l'avez demandé de le faire sur une grande entrée), lisez la matrice dans une liste de la liste qui a pris les données comme une paire d'un tuple, et la MXN Coord comme la partie du tuple, Et puis Quicksort la matrice une fois, puis la trouvez par valeur. p>
alternativez, si la valeur de chaque emplacement individuel est unique, mélanger les données MXN dans un dictionnaire figurant sur la valeur, puis passer à l'entrée du dictionnaire du MXN en fonction de la clé de l'entrée (ou de la hachage de la clé de l'entrée). p>
EDIT: P>
Notez que la réponse que je donne ci-dessus est valide si vous allez regarder à travers la matrice plus d'une fois. Si vous n'avez besoin que de l'analyser une fois, ceci est aussi rapide que vous pouvez le faire: P>
for (int i = 0; i<M; i++) for (int j=0; j<N; j++) if (mat[i][j] == value) return tuple(i,j);
Eh bien, les diagonales semblent être triées, ne remarquaient pas cela auparavant. Mais le genre n'est pas par des diagonales, il est plus simple. Chaque rangée est triée et chaque colonne par elle-même est triée. Mais comme vous avez dit lire une ligne ne donne aucune information sur la ligne suivante.
ni une colonne sur la colonne suivante. Vous ne pouvez faire aucune hypothèse sur la vitesse de la recherche d'un élément, sans itération sur tout le monde. J'essaie de rechercher la méthode la plus rapide possible de trouver une valeur. Un O (N) semble être le plus rapide, mais si vous allez faire ce que j'ai suggéré, ce n'est valable que si vous cherchez beaucoup de valeurs. Sinon, si vous faites simplement l'analyse une fois, il est plus rapide de simplement pour la boucle deux fois sur le MXN avec un avort précoce trouvé.
Mais dès que vous devez trouver deux valeurs, la voie de la mine donnée dans la réponse est plus rapide qu'un double pour boucle
C'est aussi ce que je pense. Je pense que O (n) est assez bon dans ce cas, je ne peux voir aucun moyen de la trouver avec une meilleure complexité sans ajouter une autre structure de données. Et je n'ai pas non plus besoin de rechercher deux fois, dans l'affectation, il affirme que si la valeur apparaît plus d'une fois, je n'ai encore besoin de trouver qu'une seule instance.
Dans le journal, vous pouvez obtenir une gamme de lignes capables de contenir la cible (recherche binaire de la première valeur des lignes, une recherche binaire sur la dernière valeur des lignes, gardez uniquement ces lignes dont la première <= cible et dernière> cible ) deux recherches binaires sont toujours O (log m)
Ensuite, dans O (journal de bord), vous pouvez explorer chacune de ces lignes, avec une nouvelle recherche binaire!
qui le fait o (logm x logn)
Tadaaaa
Vous pouvez faire une recherche binaire, gardez simplement le pointeur inférieur sur le côté gauche et le pointeur supérieur sur le côté droit. Tout entre les deux à la fin est l'ensemble des lignes à explorer.
Pour simplifier les mathématiques, supposons que la taille est NXN. Maintenant, prenons un mauvais cas: disons que toutes les valeurs de la première rangée sont plus petites que 10 et toutes les valeurs de la dernière ligne sont plus grandes que 100 et que je recherche une cible = 50. Dans ce cas, je ne peux pas éliminer aucune ligne, donc je n'ai toujours pas à des rangées de recherche binaire et qui me donnera O (n * logn)
@Bob ~ Ouais, nous savons, mais vous commencerez ensuite la recherche binaire de la dernière ligne à la première. Vous connaissez les recherches binaires droite? en.wikipedia.org/wiki/binary_search_algorithm
I Deuxième Bob, cette réponse est incorrecte et mérite un vote en bas. La complexité des cas pire est toujours O (m.log (n)), la première recherche pourrait très bien renvoyer l'ensemble des rangées.
Bownvote aussi bien. O (n) la notation signifie la plus complexité des cas et ce n'est pas O (logm x logn). Vous pouvez faire valoir que l'heure prévue est plus faible avec cette solution, mais elle maintient toujours la complexité du pire des cas O (n * log n).
Ouais, l'algorithme donne une réponse correcte, mais le pire des cas d'exécution est totalement faux.
Votre matrice ressemble à ceci: et a suivi des propriétés suivantes: p> donc la valeur dans la plupart des angles (par exemple . afin que nous puissions essayer d'utiliser une recherche binaire: p> ALGORITHM peut donc ressembler à ceci: P> i code>) est toujours le plus grand de matrice entière
et cette propriété est récursive si vous divisez la matrice en 4 morceaux égaux. P>
input: X - value to be searched
until found
divide matrix into 4 equal pieces
get e,f,h,i as shown on picture
if (e or f or h or i) equals X then
return found
if X < e then quarter := 1
if X < f then quarter := 2
if X < h then quarter := 3
if X < i then quarter := 4
if no quarter assigned then
return not_found
make smaller matrix from chosen quarter
Le seul problème est que la matrice finale est de taille MXN, et elle n'a pas l'air (à première vue) comme cette méthode échelle bien. Cependant, vous pouvez être sur quelque chose, peut-être que les gens de Math.StaCkeXchange.com peuvent vous aider à le rincer?
"Si x
Il serait tout à fait surprenant que c'était une complexité optimale pour la recherche d'une matrice unidimensionnelle triée, ce que nous aurions si toute la matrice MXN a été triée avec tous les éléments de la ligne que je suis plus petit que tout éléments sur i + 1 pour toutes les lignes. La complexité doit être pire que ça.
public static boolean find(int a[][],int rows,int cols,int x){
int m=0;
int n=cols-1;
while(m<rows&&n>=0){
if(a[m][n]==x)
return1;
else if(a[m][n]>x)
n--;
else m++;
}
}
c'est une mauvaise réponse
Je ne sais vraiment pas si l'une des réponses sont les réponses optimales. Je vais dessus.
Je pense que la complexité de temps est 2 * (log M + journal n).
Vous pouvez réduire la constante, si la matrice d'entrée est un carré (N * N), par une recherche binaire le long de la diagonale.
Désolé, c'est faux. Imaginez une matrice 4x4 où la première ligne et la première colonne ressemblent à 1 2 3 10 , et vous êtes invité à rechercher 7. Vous diriez que c'est sur la 3ème rangée et 3ème col, mais Ce n'est pas le cas. 7 pourrait être à (2, 2) et tout le reste des cellules peut être 999 ...
Qu'en est-il d'obtenir la diagonale, puis de la recherche binaire sur la diagonale, démarrez de bas à droite Vérification si elle est ci-dessus, si oui, prenez la position de la matrice diagonale comme la colonne qu'il se trouve, sinon, vérifiez s'il est ci-dessous. Chaque fois que vous exécutez une recherche binaire sur la colonne une fois que vous avez un coup sur la diagonale (en utilisant la position de la matrice de la diagonale comme indice de colonne). Je pense que c'est ce qui a été indiqué par @ user942640
Vous pouvez obtenir la période d'exécution de ce qui précède et si nécessaire (à un moment donné) échanger l'algo pour effectuer une recherche binaire sur la matrice diagonale initiale (cela prend en compte ses éléments N * N et obtenir une longueur de x ou y est O (1) comme x.length = y.length. Même sur un million * Million de recherche binaire de la diagonale si elle est inférieure à la moitié de la diagonale, si ce n'est pas moins la recherche binaire vers l'endroit où vous ( C'est un léger changement à l'algo lors de la recherche binaire le long de la diagonale). Je pense que la diagonale est meilleure que la recherche binaire dans les rangées, je suis juste fatigué pour le moment de regarder les mathématiques :)
En passant, je crois que le temps de fonctionnement est légèrement différent de l'analyse que vous décririez en termes de best / pire / avg de cas et de temps contre la taille de la mémoire, etc. La question serait donc mieux indiquée dans «Quel est le meilleur Temps de fonctionnement dans le pire analyse des cas ', car dans le meilleur des cas, vous pouvez faire une analyse linéaire brute et que l'article pourrait être dans la première position, ce serait une meilleure "heure d'exécution" que la recherche binaire ...
Voici une limite inférieure de n . Commencez par un tableau non formé A de longueur n . Construire une nouvelle matrice m selon la règle suivante: La diagonale secondaire contient la matrice A, tout ce qui est au-dessus de celui-ci est moins infini, tout ci-dessous est plus l'infini. Les lignes et les colonnes sont triées et à la recherche d'une entrée en M est la même que de rechercher une entrée dans un.
Ceci est dans la veine de La réponse de Michal (à partir de laquelle je vais voler le graphique sympa).
matrice : P> min et max sont les plus petites et les plus grandes valeurs, respectivement. "MID" n'est pas nécessairement la moyenne / médiane / quelle que soit la valeur. P> Nous savons que la valeur au milieu est> = toutes les valeurs du quadrant II et Ainsi, si la valeur cible est inférieure à la mi-journée, nous devons rechercher des quadrants I, II et III. Si la valeur cible est supérieure à la mi-moyenne, nous devons rechercher des quadrants I, III et IV. P> L'espace réduit à 3/4 son précédent à chaque étape: p> n * ( 3/4) x sup> = 1 p> n = (4/3) x sup> p> x = journal 4 / 3 sub> (n) p> logarithmes diffèrent d'un facteur constant, c'est donc O (log (n)). P> find(min, max, target)
if min is max
if target == min
return min
else
return not found
else if target < min or target > max
return not found
else
set mid to average of min and max
if target == mid
return mid
else
find(b, f, target), return if found
find(d, h, target), return if found
if target < mid
return find(min, mid, target)
else
return find(mid, max, target)
solution JavaScript:
Pourriez-vous éventuellement partager un exemple de données? Vous avez sûrement reçu un échantillon.
"Toutes ses rangées sont triées et toutes ses colonnes sont triées individuellement": qu'est-ce que cela signifie?
Les valeurs de chaque ligne sont triées et les valeurs de chaque colonne sont triées.
Je pense qu'il signifie que la valeur en haut à gauche (1,1) sera la plus petite et la valeur en bas à droite (N, M) sera la plus grande. Les rangées et les colonnes sont toutes deux triées.
@sagar Mais ce n'est pas l'exemple donné par le professeur. Sinon, il avait la méthode la plus rapide ci-dessus (vérifiez d'abord la fin de la ligne, puis continuez) en outre, la vérification de la fin de la ligne médiane est d'abord plus rapide, un peu de recherche binaire.
Aah droit. n'a pas vu le numéro 8/7
duplicata potentiel de Compte tenu d'un tableau 2D trié dans l'ordre croissant de gauche à droite et de haut en bas, quelle est la meilleure façon de rechercher un numéro cible?
Dupe Question a une réponse qui prouve Big_omega (min (n, m)) la complexité inférieure liée: Stackoverflow.com/questions/2457792 / ... . Donc, pas de solution logarithmique lorsque N et M sont proches. Vos exemples de données semblent potentiellement mieux, dans le sens où il dispose également de la propriété que chaque diagonale est triée, mais vous n'indiquez pas cette contrainte dans la question.
@stevejessop C'est parce qu'il va par ce qui lui a été donné par son professeur. En outre, il semble être une classe axée sur les algues et non sur la mise en œuvre.
Avez-vous déjà reçu cela résolu avec succès? Avez-vous toujours besoin d'aide avec cela?
Dupliquer possible de Compte tenu d'un tableau 2D trié dans l'ordre croissant de gauche à droite et de haut en bas, quelle est la meilleure façon de rechercher un numéro cible?