Algoritmo per trovare lenth della sequenza più lunga di spazi vuoti in una determinata stringa

Question

Cerchi un algoritmo per trovare la lunghezza della sequenza più lunga di spazi vuoti in una determinata stringa esaminando il minor numero possibile di caratteri?

Suggerimento: il programma dovrebbe diventare più veloce all'aumentare della lunghezza della sequenza di spazi vuoti.

so la soluzione che è O (n) .. Ma cercando la soluzione più ottimale

Answer 1

Ma nel caso peggiore (quando tutti i personaggi sono vuote) è necessario esaminare ogni personaggio. Quindi non può essere migliore di O (n) in complessità.

Razionale: si supponga che l'intera stringa sia vuota, non sono stati esaminati N caratteri e le uscite degli algoritmi n. Quindi se qualsiasi carattere non esaminato non è vuoto, la tua risposta sarebbe sbagliata. Quindi per questo particolare input devi esaminare l'intera stringa.

Answer 2

Non sarà possibile trovare una soluzione che sia una complessità più piccola di O (n) perché è necessario passare attraverso ogni carattere nel caso peggiore con una stringa di input che abbia al massimo 0 o 1 spazio bianco consecutivo, o è completamente bianco.

È tuttavia possibile eseguire alcune ottimizzazioni, ma verrà comunque considerato O (n).

Ad esempio:

Sia M l'attuale corrispondenza più lunga misura in cui si passa attraverso la vostra lista. Supponiamo anche di poter accedere agli elementi di input in O (1), ad esempio se hai un array come input.

Quando si vede uno spazio non vuoto, è possibile saltare gli elementi M se lo current + M non è uno spazio bianco. Sicuramente non è possibile contenere all'interno spazi vuoti più lunghi di M.

E quando si vede un carattere bianco, se lo current + M-1 non è uno spazio vuoto si sa che non si hanno le esecuzioni più lunghe o si può saltare anche in quel caso.

Answer 3

In ogni caso, il caso peggiore sarà sempre o (n) - se questi spazi vuoti si trovano sull'ultima parte della stringa ... (o l'ultima parte "verificata" della stringa).

Answer 4

L'idea ovvia: puoi saltare da K + 1 posti (dove K è l'attuale sequenza di spazio più lunga) e scansionare indietro se hai trovato uno spazio.

In questo modo si dispone di qualcosa (n + n/M)/2 = n (M + 1)/posizioni 2M controllate.

Modifica:
Un'altra idea sarebbe quella di applicare una sorta di ricerca binaria. Questo è come segue: per un dato k si esegue una procedura che controlla se esiste una sequenza di spazi con lunghezza > = k. Questo può essere ottenuto in passi O (n/k). Quindi, si tenta di trovare il massimo k con la ricerca binaria.

Edit:
Durante le conseguenti ricerche, si può utilizzare la conoscenza che la sequenza di una certa lunghezza k già esistono, e iniziare a saltare a k fin dall'inizio.

Answer 5

Non c'è modo di renderlo più veloce di O(N) nel peggiore dei casi. Tuttavia, ecco alcune ottimizzazioni, ipotizzando l'indicizzazione basata su 0.

1. Se si dispone già di una sequenza completa di L spazi vuoti (da completo intendo una sequenza che non è una sottosequenza di una sequenza più ampia), e L è almeno grande quanto la metà delle dimensioni della stringa, è può fermarsi.
2. Se si dispone di una sequenza completa di spazi vuoti L, quando si preme uno spazio nella posizione i controllare se il carattere nella posizione i + L è anche uno spazio. In tal caso, continuare la scansione dalla posizione i in avanti poiché è possibile che si trovi una sequenza più grande, tuttavia, se si incontra un non spazio fino alla posizione i + L, è possibile passare direttamente a i + L + 1. Se non è uno spazio, non è possibile creare una sequenza più grande a partire da i, quindi eseguire la scansione in avanti a partire da i + L + 1.
3. Se si dispone di una sequenza completa di spazi di lunghezza L, e siete in posizione i e devi k posizioni a sinistra per esaminare, e k <= L, ci si può fermare la ricerca, come, ovviamente, non c'è modo sarete in grado di trovare qualcosa di meglio.

Per provare che non è possibile renderlo più veloce di O(N), considerare una stringa che non contiene spazi. Dovrai accedere a ciascun personaggio una volta, quindi è O(N). Lo stesso con una stringa che non contiene nient'altro che spazi.