È possibile contare le cifre distinte in un numero in tempo costante O(1)?Conteggio cifre distinte
Supponiamo che l'uscita n=1519 sia 3 in quanto ci sono 3 cifre distinte (1,5,9).
L'ho fatto in tempo O(N) ma qualcuno sa come trovarlo nel tempo O(1)?
Presumo N è il numero di cifre di n. Se la dimensione di n è illimitata, non è possibile eseguire in generale in O (1).
Prendere in considerazione il numero n=11111...111, con 2 trilioni di cifre. Se cambio una delle cifre da 1 a 2, non c'è modo di scoprirlo senza guardare in qualche modo ogni singola cifra. Quindi l'elaborazione di un numero con 2 trilioni di cifre deve prendere (dell'ordine di) 2 trilioni di operazioni almeno e, in generale, un numero con cifre N deve assumere (dell'ordine di) operazioni N almeno.
Tuttavia, per quasi tutti i numeri, l'algoritmo semplice O(N) termina molto rapidamente perché è possibile interrompere appena si arriva a 10 cifre distinte. Quasi tutti i numeri di lunghezza sufficiente avranno tutte le 10 cifre: ad es. la probabilità di non terminare con la risposta '10' dopo aver visto le prime 100 cifre è di circa 0.00027, e dopo le prime 1000 cifre è circa 1.7e-45. Ma sfortunatamente, ci sono alcune stranezze che rendono il caso peggiore O(N).
Se il numero dato si adatta alla parola macchina sottostante, si ha un algoritmo O (1) banale; vale a dire guardare la risposta in una tabella di ricerca come suggerito (iron in guancia) da Jon Skeet. Per N di dimensioni generiche, il mio punto rimane, credo. –
Mi dispiace, non capisco il tuo punto. Qualunque sia la dimensione della parola, saranno alcune dimensioni finite fisse. Quindi le prestazioni big-Oh di qualsiasi algoritmo che ha a che fare con dati di dimensioni arbitrarie saranno indipendenti dalla dimensione della parola. Fare aritmetica sulle parole non aiuta, anche se tali operazioni possono essere fatte in O (1) parola per parola, perché il numero di parole richieste per esprimere il numero n è esso stesso O (N). –
Dopo aver visto che qualcuno in realtà ha postato una risposta seria a questa domanda, preferisco ripetere il mio imbroglio qui, che è un caso particolare della risposta descritta da @SimonNickerson:
O (1) non è possibile, a meno che non si è in radix 2, perché in questo modo, ogni numero diverso da 0 ha sia 1 e 0, e quindi la mia "soluzione" non funziona solo per gli interi ...
EDIT
Che ne dici di 2^k - 1? Non è tutto 1?
Drat! Vero ... avrei dovuto sapere che quando qualcosa sembra così facile, è in qualche modo imperfetto ... Se avessi risolto il caso tutti 0, avrei dovuto coprire anche il caso 1.
Fortunatamente questo caso può essere testato abbastanza rapidamente (se l'aggiunta e il bit AND sono considerati un'operazione O (1)): se x è il numero da testare, calcolare in questo modo: y=(x+1) AND x. Se y=0, quindi x=2^k - 1. perché questo è l'unico caso in cui tutti i bit devono essere capovolti dall'aggiunta. Naturalmente, questo è un po 'imperfetto, poiché con lunghezze di bit che superano la larghezza del bus, gli operatori bit a bit non sono più O (1), ma piuttosto O (N).
Allo stesso tempo, penso che possa essere ridotto a O (logN), suddividendo il numero in blocchi di larghezza del bus e AND-ing insieme a quelli vicini, ripetendo finché ne rimane uno solo: se ci non erano 0 nel numero testato, l'ultimo sarà pieno anche 1s ...
EDIT2: Ho sbagliato ...Questo è ancora O (N).
Che ne dici di 2^k - 1? Non è tutto 1? –
Drat! Vero ... avrei dovuto sapere che quando qualcosa sembra così facile, è in qualche modo imperfetto ... Se avessi risolto il caso tutti 0, avrei dovuto coprire anche il caso 1. Fortunatamente questo caso può essere testato abbastanza rapidamente (se l'aggiunta e il bit AND sono considerati un'operazione di O (1)): se x è il numero da testare, calcola y in questo modo: 'y = (x + 1) AND x'. Se 'y = 0', quindi' x = 2^k - 1'. perché questo è l'unico caso in cui tutti i bit devono essere capovolti. Naturalmente, questo è un po 'imperfetto, poiché con lunghezze di bit che superano la larghezza del bus, gli operatori bit a bit non sono più O (1), ma piuttosto O (N) ... – ppeterka
Devi visitare ogni cifra. Costante significa che useresti lo stesso tempo per calcolare n = 1 come n = 123456789 –
ingannare sull'input (supponendo che il tempo necessario per dividere la stringa e trasformarlo in un set possa essere lasciato fuori dal gioco) – BigMike
O (N) per cosa N? grandezza di n? numero di cifre (ad es. registro)? – Kevin