27.10.2013, 11:52
Wenn du es in einen Prefixtree packst ist es schnell O(log n). Bisher ist es lineare Suche O(n).
Wem das O(x) nichts sagt, das ist die Komplexitätsklasse.
Beispiel:
100 Einträge durchsuchen bei O(n) braucht 100 Operationen.
100 Einträge durchsuchen bei O(log n) braucht log 100 = 2 Operationen.
Richtig schnell wird es aber erst bei vielen Einträgen
10000 Einträge durchsuchen bei O(n) braucht 10000 Operationen.
10000 Einträge durchsuchen bei O(log n) braucht log 10000 = 4 Operationen.
Wem das O(x) nichts sagt, das ist die Komplexitätsklasse.
Beispiel:
100 Einträge durchsuchen bei O(n) braucht 100 Operationen.
100 Einträge durchsuchen bei O(log n) braucht log 100 = 2 Operationen.
Richtig schnell wird es aber erst bei vielen Einträgen
10000 Einträge durchsuchen bei O(n) braucht 10000 Operationen.
10000 Einträge durchsuchen bei O(log n) braucht log 10000 = 4 Operationen.