Sostituzione di confronti di stringhe con ricerche nel dizionario

0

Dato 2 stringhe s1 e s2, se eseguo un semplice controllo di uguaglianza, è considerato come O (n) quando si calcola l'efficienza dell'algoritmo. Quindi, se sto usando un approccio a forza bruta per substring ruotato domanda l'efficienza è O (n ^ 2) (prendi la seconda sottostringa, ruota di 1 e verifica.Ripeti fino a rotazioni = strlen o abbinata)

Tuttavia, una ricerca del dizionario è considerata O (1). Se invece usassi un dizionario con il solo elemento avente un valore fittizio e una chiave = s1. Quindi, invece di fare una comparazione di stringhe ho verificato l'esistenza di s2 nel dizionario, la mia complessità non sarebbe andata a O (n)?

Intuitivamente non ha senso per me, quindi suppongo che una delle mie supposizioni sia errata ...

    
posta Akash 06.05.2014 - 19:13
fonte

1 risposta

2

Un dizionario deve anche fare almeno un confronto. Se la lunghezza della stringa è la variabile di interesse, questo deve essere preso in considerazione e poiché il confronto è O (strlen) una ricerca richiede anche O (strlen). Diciamo che le ricerche nella tabella hash (ci si aspetta) richiedono O (1) volte per quanto riguarda il numero di voci .

A parte: una tabella hash con una singola chiave non risolverebbe il problema della sottostringa ruotata. Fare questo una volta per ogni rotazione richiede ancora tempo O (strlen ^ 2) in totale, dato che fai confronti O (strlen) che richiedono O (strlen) di tempo ciascuno (vedi sopra). Puoi, tuttavia, riempire una tabella con tutto delle rotazioni n e quindi eseguire una ricerca, e sotto gli stessi presupposti che implicano la ricerca O (1) in termini di numero di chiavi, questo richiede O (strlen) tempo in totale. Tuttavia, richiede anche lo spazio O (strlen ^ 2), che è uno svantaggio.

Il motivo per cui questo funziona per una singola ricerca in una singola tabella hash di tutte le rotazioni (ma non per fare molte ricerche nelle tabelle hash a elemento singolo) è che l'hashing distribuisce a basso costo le stringhe in intervalli disgiunti, così che quasi tutti i confronti sono evitati. Le stringhe con diversi hash vengono abbattute con un calcolo hash e ricerca di array.

    
risposta data 06.05.2014 - 19:21
fonte

Leggi altre domande sui tag