Perché gli algoritmi di divisione e conquista spesso vengono eseguiti più rapidamente della forza bruta?

Question

Perché gli algoritmi di divisione e conquista spesso vengono eseguiti più rapidamente della forza bruta? Ad esempio, per trovare la coppia più vicina di punti. So che puoi mostrarmi la prova matematica. Ma intuitivamente, perché succede? Magia?

In teoria, è vero che "divide et impera è sempre meglio della forza bruta"? Se non lo è, c'è qualche controesempio?

Answer 1

Per la tua prima domanda, l'intuizione dietro divide et impera è che in molti problemi la quantità di lavoro da svolgere si basa su una proprietà combinatoria dell'input che scala in modo più che lineare.

Ad esempio, nel problema del paio di punti più vicino, il tempo di esecuzione della risposta forza bruta è determinato dal fatto che è necessario osservare tutte le coppie di punti possibili (n).

Se si prende qualcosa che cresce in modo quadratico e tagliato in due pezzi, ognuno dei quali è la metà della dimensione di prima, ci vuole un quarto del tempo iniziale per risolvere il problema in ogni metà, quindi risolvere il problema in entrambi la metà richiede circa la metà del tempo richiesto per la soluzione di forza bruta. Tagliarlo in quattro pezzi impiegherebbe un quarto del tempo, tagliandolo in otto pezzi l'ottavo del tempo, ecc.

La versione ricorsiva finisce per essere più veloce in questo caso perché ad ogni passo, evitiamo di fare molto lavorare dalla gestione di coppie di elementi assicurando che non ci siano troppe coppie che dobbiamo effettivamente controllare. La maggior parte degli algoritmi che hanno una soluzione divide et impera finiscono per essere più veloci per una ragione simile.

Per la seconda domanda, no, gli algoritmi di divisione e conquista non sono necessariamente più veloci di algoritmi a forza bruta. Considera il problema di trovare il valore massimo in una matrice. L'algoritmo a forza bruta impiega O (n) tempo e utilizza lo spazio O (1) mentre esegue una scansione lineare sui dati. L'algoritmo divide et impera è riportato qui:

• Se l'array ha un solo elemento, quello è il massimo.
• Altrimenti:
  • Tagliare la matrice a metà.
  • Trova il massimo in ogni metà.
  • Calcolare il massimo di questi due valori.

questo richiede tempo O (n) pure, ma usa O (log n) di memoria per lo spazio di stack. In realtà è peggio del semplice algoritmo lineare.

Come altro esempio, lo maximum single-sell profit problem ha una soluzione divide et impera, ma la soluzione di programmazione dinamica ottimizzata è più veloce sia in termini di tempo che di memoria.

Spero che questo aiuti!

Answer 2

Vi consiglio di leggere il capitolo 5 di Algorithm Design, spiega molto bene divide-e-conquista.

Intuitivamente, per un problema, se è possibile dividerlo in due sotto-problemi con lo stesso schema dell'origine uno, e la complessità temporale per unire i risultati dei due sotto-problemi nel risultato finale è in qualche modo piccola , quindi è più veloce di risolvere il problema originale completo con la forza bruta.

Come detto in Algorithm design, in realtà non si può guadagnare troppo da divide et impera, in termini di tempo, in generale si può solo ridurre complessità temporale dal più alto polinomiale per abbassare polinomiale (ad esempio da O (n^3) a O (n^2)), ma difficilmente da esponenziale a polinomiale (ad es. da O (2^n) a O (n^3)).

Penso che il massimo che si può ottenere da divide e conquistare è la mentalità per la risoluzione dei problemi. È sempre un buon tentativo di rompere il grande problema originale fino a problemi secondari più piccoli e più facili. Anche se non ottieni un tempo di esecuzione migliore, ti aiuta ancora a pensare al problema.