Aus Neugier, was ist ListBox.FindString (String) Worst-Case-Laufzeit? MSDN gibt dies nicht in seinen API-Dokumenten an.ListBox.FindString Was ist die Worst-Case-Laufzeit? O (n), O (n log n), O (1) & rarr;
Ich habe einen starken Verdacht, es ist O (n), ich habe eine sortierte Liste und O (log n) oder O (1) wäre nett, gibt es eine Möglichkeit zu ändern, welche Sortieralgorithmus FindString zur Laufzeit verwendet?
Wenn Sie genügend Strings in der ListBox haben, so dass das große O von FindString() funktioniert, müssen Sie einen anderen Weg suchen, Ihre Strings zu speichern.
"Sucht das erste Element in der ListBox , die mit dem angegebenen String beginnt."
Das riecht wie eine lineare Suche vom Anfang der Liste, aber es gibt keine Möglichkeit, sicher zu wissen.
Sie können nicht ändern, welchen Algorithmus ListBox verwendet, aber Sie können ListBox erweitern und Ihre erweiterte Klasse haben, was Sie wollen. : D
Unabhängig davon, ob es eine gute Idee ist, eine große Anzahl von Elementen in einer Listbox bis zu dem Punkt zu haben, wo es wichtig wäre (Es könnte für den Benutzer umständlich sein, abhängig von Ihrer Implementierung.), Gehe ich O (n) zu erraten, da ich glaube, dass es eine teilweise Übereinstimmung macht, die Groß-/Kleinschreibung nicht beachtet.
Eigentlich Sie können sehen, was das Verfahren der Fall ist, wie Microsoft ihre .net Basisklasse Quellcode verfügbar über 'Microsoft Reference Source Code' machen (clicky) - Sie in BCL-Code in VS Schritt kann (auch viel von das BCL-Zeug ist über Rotor verfügbar, die Open-Source-Implementierung von .net, aber WinForms-Code ist nicht verfügbar IIRC).
Untersuchen Sie den Code (was ich will hier nicht nur einfügen, falls es MS-Lizenz verletzt), ist es klar, das Verfahren ist O (n) Worst-Case.
Grundsätzlich durchläuft die Methode jedes Element in der Liste und kehrt dann zum Anfang der Liste zurück, wenn das Ende erreicht ist (durch eine schlaue Verwendung des immer schönen mod (%) -Operators und eines Zählers). Offensichtlich ist dies im schlechtesten Fall O (n) (d. H. Das gesuchte Element ist nicht in der Liste), wo es über jedes Mitglied der Liste iterieren müsste.
Okay, aber wie wäre es mit der Beantwortung der Frage? – Alan
Die Laufzeit für ListBox.FindSTring() ist weitgehend irrelevant - UI-Textfelder sind entworfen, um eine kleine Anzahl von Strings zu halten, so dass lineare Suche akzeptabel ist. Fast jeder Algorithmus ist schnell für ein kleines N. Wenn N sehr groß ist, sollten Sie ListBox nicht als Datenspeicher verwenden. – Michael
Ich weiß, ich würde alles in einer HashTable für seine fantastische O (1) Lookup speichern, aber ich habe> 100.000 "Wörter", und sowohl ListBox und HashTable müssen im Speicher gehalten werden :( – Kai