J'ai me suis posé la question de la complexité temporelle du pire cas pour déterminer si deux tableaux non ordonnés contiennent les mêmes éléments. Les éléments peuvent être de n'importe quel type. Nombres, chaînes de caractères, objets personnalisés... etc, mais supposons que les éléments soient à la fois ordonnables et hashables.
J'ai pensé à trois méthodes, bien expliquées dans ce post stackoverflow. Qui sont 1) utiliser un hash 2) utiliser le tri 3) parcourir simplement.
Le post a indiqué qu'il est possible d'atteindre un temps de complexité en O(n) si les données sont hashables, cependant, je pense que ce n'est pas tout à fait exact car l'insertion et la recherche dans un hash ne sont pas des opérations en temps de complexité O(1). C'est en moyenne O(1), s'il n'y a pas de collision, mais c'est en O(n) à la fois pour l'insertion et la recherche (en théorie). Donc, s'il y a beaucoup de collisions, utiliser un hash pour dire que deux tableaux sont égaux coûtera O(n^2). (veuillez me corriger si je me trompe.)
Il me semble donc que dire que deux tableaux sont égaux coûtera autant que le tri des tableaux, ce qui, sans aucune connaissance sur le tableau, coûterait O(nlogn). (en supposant que comparer deux éléments égaux coûtera toujours O(1))
Est-il possible de dire que deux tableaux sont égaux en temps de complexité O(n) dans le pire des cas? J'apprécierai tout commentaire, indications de doublons, références à un article. Merci!
Voici mon code pour comparer si deux tableaux sont égaux. (C'est en ruby et cela fonctionne, mais veuillez le considérer davantage comme un pseudo-code)
Un. Comparaison par hachage - en moyenne, O(n), pire des cas, O(n^2)
def compare_by_hashing(list1, list2)
hash1 = {}
list1.each do |item|
hash1[item] ||= 0
hash1[item] += 1
end
hash2 = {}
list2.each do |item|
hash2[item] ||= 0
hash2[item] += 1
end
hash1.each do |key, hash_1_value|
return false if hash_1_value != hash2[key]
end
return true
end Deux. Comparaison par tri. Pire des cas O(nlogn)
# 2. comparer par tri. Pire des cas `O(nlogn)`
def compare_by_sorting(list1, list2)
list1.sort
list2.sort
list1.each_with_index do |list_1_item, index|
return false if list_1_item != list2[index]
end
return true
end Trois. Comparaison en parcourant simplement. Pire des cas O(n^2)
def compare_by_looping(list1, list2)
list1.each do |item|
if list2.include? item
list2.delete item
else
return false
end
end
return true Édition
J'apprécie et je comprends les réponses et les commentaires selon lesquels les opérations de hachage montrent normalement une complexité temporelle en O(1) et que les scénarios du pire des cas sont très peu susceptibles de se produire. Cependant, puisqu'ils peuvent de toute façon se produire, je ne veux pas ignorer les possibilités. Je m'excuse de ne pas avoir clarifié mon point. Mon intention première était de trouver un algorithme théoriquement prouvé en O(n), pas un algorithme pratique. Merci pour votre attention. Je l'apprécie vraiment.
