Was ist die beste/schlechteste/durchschnittliche Fallkomplexität (in Big-O-Notation) einer Trie-Datenstruktur zum Einfügen und Suchen?Was ist die beste/schlechteste/durchschnittliche Fall-Big-O-Laufzeit einer Trie-Datenstruktur?
Ich denke, es ist O(K) für alle Fälle, wo K ist die Länge einer beliebigen Zeichenfolge, die eingefügt oder durchsucht wird. Wird das jemand bestätigen?
Nach Wikipedia und this source, schlimmsten Fall Komplexität zum Einsetzen und Suche nach einem Trie ist O(M) wo M ist die Länge eines Schlüssels. Ich finde keine Quellen, die die beste oder durchschnittliche Fallkomplexität von Insertion und Suche beschreiben. Wir können jedoch mit Sicherheit sagen, dass die beste und durchschnittliche Fallkomplexität O(M) ist, wobei M die Länge eines Schlüssels ist, da Big-O nur eine Obergrenze für die Komplexität beschreibt.
Es gibt einige gute Infos dazu auf Wikpedia. http://en.wikipedia.org/wiki/Trie
k: Die Länge der Zeichenfolge, die Sie suchen oder einfügen.
For Search
Worst: O(26*k) = O(k)
Average: O(k) # In this case, k is an average length of the string
Best: O(1) # Your string is just 'a'.
Die Komplexität von Trie ändert sich nicht mit der Anzahl der gesuchten Zeichenfolgen, sondern nur mit der Länge der Suchzeichenfolge. Deshalb wird Trie verwendet, wenn die Anzahl der zu suchenden Strings groß ist, wie das Durchsuchen des gesamten Vokabulars in einem englischen Wörterbuch.
For Insertion
Worst: O(26*k) = O(k)
Average: O(k)
Best: O(1)
Also ja, Sie haben Recht. Du hättest wahrscheinlich O (MN) gesehen, und das hätte dich vielleicht verwirrt, aber es redet einfach davon, wenn du N-mal mehr als O (k) -Operationen machen musst.