Qual è la complessità migliore/peggiore/caso medio (in notazione Big-O) di una struttura dati trie per l'inserimento e la ricerca?Qual è il runtime Big-O del caso migliore/peggiore/medio di una struttura dati Trie?
Penso che sia O(K) per tutti i casi, dove K è la lunghezza di una stringa arbitraria che viene inserita o ricercata. Qualcuno lo confermerà?
Secondo Wikipedia e this source, il caso peggiore complessità per l'inserimento e ricerca di un trie è O(M) dove M è la lunghezza di una chiave. Non riesco a trovare alcuna fonte che descriva la complessità del caso medio o migliore dell'inserimento e della ricerca. Tuttavia, possiamo tranquillamente dire che la complessità del caso migliore e media è O(M) dove M è la lunghezza di una chiave, poiché Big-O descrive solo un limite superiore della complessità.
Ci sono alcune grandi informazioni su questo su Wikpedia. http://en.wikipedia.org/wiki/Trie
k: la lunghezza della stringa che si cerca o si inserisce.
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'.
La complessità di Trie non cambia con il numero di stringhe che si cercano, solo con la lunghezza della stringa di ricerca. Ecco perché Trie viene usato quando il numero di stringhe da cercare è ampio, come cercare gli interi vocabolari in un dizionario inglese.
For Insertion
Worst: O(26*k) = O(k)
Average: O(k)
Best: O(1)
Quindi, sì, hai ragione. Probabilmente avresti visto O (MN) e questo potrebbe averti confuso, ma sta semplicemente parlando di quando devi fare N sopra operazioni O (k).