Donné 3 array trié. Trouver 3 éléments, un de chaque tableau tel que a + b = c. Peut-il être fait moins de O (n^3) complexité de temps? Aidez-moi, s'il vous plaît.Recherche dans plusieurs tableaux triés et sa complexité
Cela peut être fait dans la complexité O (N^2 * logN) en itérant à travers 2 des tableaux pour a et b et la recherche binaire pour c dans le troisième tableau.
Une autre méthode serait O (N^2) en insérant les éléments de l'un des tableaux dans un hachage, itérer pour a et b dans les deux autres tableaux et regarder si c = (a + b) existe dans le hacher.
Appelez les trois tableaux A, B et C, et les éléments a, b et c.
Tout en bouclant à travers les deux premiers tableaux, puisque si a est fixe, b peut seulement augmenter, c peut également augmenter.
Vous n'avez donc pas besoin de faire une boucle C chaque fois que vous avez une paire de a et b; il suffit de boucler C tout en bouclant si B fera l'affaire.
Supposons maintenant que les trois tableaux ont une longueur O (N), la complexité est en O (N^2), puisque pour chaque valeur A, vous devez passer par tous B et tous C, le nombre qui est sur).
Pour la méthode 2, existe-t-il un moyen efficace de la résoudre, étant donné que les 3 tableaux sont déjà triés? – Neel
Vous ne pouvez pas générer les paires (a, b) mieux que O (N^2) ... La recherche dans le hachage est O (1) – gabitzish