Ich bin heute nur auf diese Frage gestoßen und habe nach einer Lösung gesucht, die besser ist als O (N), aber ich konnte keine Lösung finden.
Gesucht durch SO aber konnte diese Frage nicht finden.
Gibt es eine bessere Lösung als O (n) oder ist es ein Problem, das nicht besser gelöst werden kann?
Mein erster Gedanke war die binäre Suche, aber wieder muss man sie sortieren, was wiederum & gt; n ist. Ich dachte auch daran, Quicksort nur für die Hälfte des Arrays zu verwenden, zu dem das Suchelement gehören könnte, aber wieder machen wir zuerst n Vergleiche und werfen die andere Hälfte erst später weg. Erhalte ich das richtig oder schaue ich die Lösung in eine falsche Richtung?
Ich habe für eine Lösung in C ++ und keine Javascript IndexOf () oder C # Array.find () oder LINQs versucht.
Mach es parallel. Teilen Sie das Array in Stücke und suchen Sie parallel. Die Komplexität wird O (n) sein, aber die Laufzeit wird viel kürzer sein. Eigentlich wird es proportional zu nein sein. von Prozessoren, die Sie haben.
Sie können Parallel Patterns Library in C ++ verwenden
Sie haben Recht, der schnellste Weg besteht darin, einfach durch das Array zu iterieren und danach zu suchen. Ohne weitere Informationen gibt es nichts Besseres, was Sie tun können.
Es sei denn, Sie haben einen Quantencomputer , das heißt.
Tags und Links algorithm visual-c++