Trouver un nombre dans une matrice triée (Lignes n Colonnes) en O(log n)

Question

Disons que j'ai une matrice ( MxN ) dont les lignes et les colonnes sont triées.

1. Tous les éléments de chaque rangée sont classés par ordre croissant.
2. Tous les éléments de chaque colonne sont classés par ordre croissant.
3. Tous les éléments sont des entiers

4. Aucune autre hypothèse ne peut être formulée

   Exemple :

   [1 5 8 20]

   [2 9 19 21]

   [12 15 25 30]

Je dois trouver si un nombre donné est présent ou non dans la matrice (recherche de base). J'ai un algorithme qui fonctionne O(n)

int row = 0;
int col = N-1;

while (row < M && col >= 0) {
  if (mat[row][col] == elem) { 
    return true;
  } else if (mat[row][col] > elem) { 
    col--;
  } else { 
    row++;
  } 
}

Mais on m'a demandé O(log (MxN)) == O(Log(n)) solution. Des idées ?

Answer 1

Une solution O(log (M * N)) n'est pas possible pour cette tâche.

Examinons une tâche simplifiée : dans une matrice carrée "triée", supposez que tous les éléments situés au-dessus de la diagonale secondaire (vert) sont inférieurs à un nombre donné, que tous les éléments situés au-dessous de la diagonale secondaire (rouge) sont supérieurs à un nombre donné, et qu'il n'y a pas d'hypothèses supplémentaires pour les éléments situés sur la diagonale secondaire (jaune).

Ni les hypothèses initiales de cette tâche, ni ces hypothèses supplémentaires ne nous disent comment les éléments sur la diagonale secondaire sont liés les uns aux autres. Ce qui signifie que nous avons juste un tableau non trié de N entiers. Nous ne pouvons pas trouver un nombre donné dans le tableau non trié plus rapidement que O(N). Donc, pour le problème original (plus compliqué) avec une matrice carrée, nous ne pouvons pas obtenir une solution meilleure que O(N).

Pour une matrice rectangulaire, étirez l'image carrée et définissez les hypothèses supplémentaires en conséquence. Ici, nous avons min(N,M) sous-réseaux triés de taille max(N,M)/min(N,M) chacun. La meilleure façon de chercher ici est d'utiliser la recherche linéaire pour trouver un ou plusieurs sous-réseaux qui peuvent contenir une valeur donnée, puis d'utiliser la recherche binaire dans ces sous-réseaux. Dans le pire des cas, il est nécessaire d'effectuer une recherche binaire dans chaque sous-réseau. La complexité est O(min(N,M) * (1 + log(max(N,M) / min(N,M)))). Donc, pour le problème original (plus compliqué) avec une matrice rectangulaire, nous ne pouvons pas obtenir une solution meilleure que O(min(N,M) * ( 1 + log(max(N,M)) - log(min(N,M)))).

Answer 2

Il n'est pas possible de faire mieux que O(n). Certains (il y en a au moins trois sur cette page) pensent pouvoir faire mieux mais c'est parce que leurs algorithmes sont faux ou parce qu'ils ne savent pas comment calculer la complexité de leur algorithme alors ils essaient de la deviner. Cet article de blog est très bon et vous expliquera les erreurs de ces types.

Ébauche d'une preuve que O(n) est optimal : considérez la matrice suivante :

1     2     3     4     5     6 … (n-2)  (n-1) (n+1)
2     3     4     5     6     7 … (n-1)  (n+1) (n+2)
3     4     5     6     7     8 … (n+1)  (n+2) (n+3)
…     …     …     …     …     … … …      …     …
(n-2) (n-1) …     …     …     … … …      …     (2n-1)
(n-1) (n+1) …     …     …     … … …      …     2n
(n+1) (n+2) …     …     …     … … (2n-1) 2n    (2n+1)

Si vous êtes à la recherche de n dans cette matrice, vous devez vérifier au moins une fois pour chaque ligne si n est dans la rangée parce que n pourrait être dans n'importe quelle rangée. (La preuve n'est pas complète mais voici l'idée)

Answer 3

Vous devez utiliser la récursion pour résoudre ce problème. Étant donné une matrice X et un nombre y, vous pouvez faire une recherche binaire de y sur la ligne centrale de X et diviser la matrice en quatre parties de telle sorte que :

A|B
---
C|D

tous les éléments de A sont inférieurs à y, tous les éléments de D sont supérieurs à y, et y peut être dans B et C. Trouvez itérativement y dans B et C.

Puisque hauteur(A)=hauteur(B) \approx = hauteur(C)=hauteur(D), taille(X)>= 2*(taille(B)+taille(C)) . Donc la complexité résultante est O(logn).

def find(X,y):
    a,b = X.shape
    i = a /2
    j = binsearch(X[i,:], y)
    if X[i,j]==y:
        return True
    else:
        return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y )

Answer 4

Puisque les lignes et les colonnes sont triées, si nous regardons le premier élément de chaque ligne, nous pouvons trouver celle qui contient le nombre que nous recherchons. Là encore, nous pouvons exploiter le fait que les éléments de chaque ligne sont triés et trouver ce nombre.
L'algorithme de recherche le plus rapide que je connaisse est la recherche binaire, dont la complexité est de O(log n). La complexité totale sera donc de O(log m + log n).
Voici un exemple, supposons que nous cherchions 28 :

 1  2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

• Nous effectuons une recherche binaire sur les éléments de la première colonne (1, 11, 21, 31, 41) et trouvons que la ligne est la troisième, car son premier élément est plus petit que notre nombre mais le premier élément de la rangée suivante est plus grand. Nombre d'étapes : 2 (21, 31, trouvé)
• Nous effectuons à nouveau une recherche binaire sur la troisième ligne (21, 22, 23, 24, 25, 26, 27, 28, 29, 30) et trouvons notre nombre. Nombre d'étapes : 2 - 3 (25, 27 ou 28, trouvés)

Answer 5

Je pense que cela peut être fait en O(log(n*n)*log(n)) temps, où n est le nombre de lignes d'une matrice carrée.

Par les propriétés de Matrix, la diagonale principale de la matrice est un tableau trié. Ainsi, nous pouvons rechercher un élément ou sa borne inférieure en O(log(n)). Maintenant, en utilisant cet élément comme pivot, nous avons 4 sous-matrices et nous pouvons dire que tous les éléments de la sous-matrice (en haut à gauche) sont plus petits, tous les éléments de la sous-matrice (en bas à droite) sont plus grands. Donc, nous pouvons supprimer cela de l'espace de recherche.

Maintenant, cherchez récursivement dans la sous-matrice (en haut à droite) et dans la sous-matrice (en bas à gauche).

Puisque, à chaque étape, nous effectuons une recherche log(n) (le long de la diagonale principale), il peut y avoir au maximum log(n*n) étapes (puisque nous réduisons l'espace de recherche de moitié à chaque étape).

Donc, complexité temporelle = O(log(n)) log(n n)).

S'il vous plaît corriger, si quelque chose est faux.

Refrences - [Book]Cracking the coding interview (Question 11.6)