Qual è la complessità del tempo prevista del controllo dell'uguaglianza di due stringhe arbitrarie?

Question

La risposta semplice (ingenua?) sarebbe o (n) dove n è la lunghezza della stringa più corta. Perché nel caso peggiore è necessario confrontare ogni coppia di caratteri.

finora così buono. Penso che tutti possiamo essere d'accordo sul controllo dell'uguaglianza di due lunghezza uguale le stringhe richiedono o (n) runtime.

Comunque molte (più?) Lingue (sto usando Python 3.7) Conservare le lunghezze delle stringhe per consentire la ricerca di tempo costanti. Quindi nel caso di due lunghezza ineguale stringhe, è possibile verificare semplicemente len(string_1) != len(string_2) in tempo costante. Puoi verificare che Python 3 faccia effettivamente questa ottimizzazione.

Ora, se stiamo controllando l'uguaglianza di due veramente stringhe arbitrarie (di lunghezza arbitraria), allora è molto più probabile (infinitamente, credo) che le corde saranno di lunghezza disuguale di uguale lunghezza. Quale (statisticamente) garantisce che possiamo quasi sempre confrontarli in tempo costante.

Quindi possiamo confrontare due stringhe arbitrarie in media o (1) media, con un caso peggiore molto raro di O (N). Dovremmo considerare i confronti di stringhe quindi essere o (1) nello stesso modo in cui consideriamo la ricerca della tabella di hash essere o (1)?

Answer 1

Per discutere la complessità del tempo prevista di un'operazione, è necessario specificare una distribuzione sugli ingressi e spiegare anche cosa intendi per $ N $ .

Uno deve essere attento, comunque. Ad esempio, considera il suggerimento nei commenti, per considerare un tipo di distribuzione su parole di lunghezza al massimo 20. In questo caso, il confronto stringa è chiaramente $ o (1) $ , dal 20 è solo una costante. Ci sono diversi modi per evitarlo:

.

• Richiedi una complessità temporale non asintotica. Poiché la complessità del tempo dipende molto dal modello di calcolo, è possibile contare (ad esempio) il numero di celle di memoria di ingresso accessibili.

• È possibile specificare una distribuzione di input che dipende da un parametro $ m $ , quindi chiedere la complessità asintotica in termini di $ m $ .

Ecco un esempio. Dato due stringhe binarie casuali di lunghezza $ N $ , ci saranno circa 4 accessi in attesa. Al contrario, se le stringhe vengono scelte a caso dalla collezione $ 0 ^ i1 ^ {ni} $ , il numero di accessi sarà all'incirca $ (2/3) n $ . Queste due distribuzioni possono essere separate anche se usiamo notazione asintotica: l'algoritmo funziona in $ o (1) $ sulla prima distribuzione, e in $ \ theta (n) $ sul secondo.

Un altro problema è il significato di $ N $ . Considera ad esempio una stringa $ 0 ^ m $ , dove $ m \ sim g (1/2) $ è una variabile casuale geometrica. Quando viene eseguito su ingressi di lunghezze $ A, B $ , il tempo di esecuzione è $ \ theta (\ min (a, b )) $ . Come dovremmo esprimere questo in termini di $ N= A + B $ ? Una scelta è quella di chiedere il tempo di esecuzione previsto dato che la lunghezza di ingresso è $ N $ . In questo caso, $$ \ mathbb {e} [\ min (a, b)]=sum_ {a= 1} ^ {n-1} \ frac {(1/2) ^ a (1/2) ^ {n-1-a }} {\ sum_ {a '= 1} ^ {n-1} (1/2) ^ {a'} (1/2) ^ {n-1-a '}} \ min (A, NA)=frac {1} {n-1} \ sum_ {a= 1} ^ {n-1} \ min (A, NA) \ circa \ frac {n} {4}, $$ Quindi il tempo di esecuzione previsto è $ \ theta (n) $ .