Che cos'è un algoritmo O (n) per risolvere questo enigma?

Question

Che cos'è un algoritmo O (n) per risolvere questo enigma?

#1 da (4 voti)
#2 da (4 voti)

1

Organizzeremo un incontro in cui tutti parleranno in senso orario attorno a un tavolo. Ci sono n persone con n punti. Ogni persona ha una preferenza di posizione (ad esempio, alcuni vogliono andare per primi, altri per ultimi, ecc.). Tutti sono seduti a caso e non possono spostarsi dalla loro posizione. Come possiamo calcolare la migliore posizione di partenza sul tavolo per soddisfare la maggior parte delle persone?

Ho una soluzione O (n ^ 2): Guarda quante persone sarebbero soddisfatte dopo aver assunto ciascuna delle posizioni 1..n come posizioni iniziali; quindi restituire la posizione che ha dato il valore massimo.

algorithms complexity puzzles big-o

posta d'alar'cop 13.03.2014 - 09:56

fonte

2 risposte

4

Se ogni persona sa esattamente quale ordine vuole entrare e l'ordine dei posti è costante, allora ognuno sa quale posizione di partenza vuole che inizi il discorso. In questo modo, puoi calcolare quante persone vogliono iniziare la conversazione in punti specifici, che è O (n) in complessità se sei la posizione preferita come indice nella matrice.

risposta data 13.03.2014 - 10:28

fonte

Leggi altre domande sui tag algorithms complexity puzzles big-o

In TDD, è una cattiva pratica passare un test con codice che supererebbe più di un test? [duplicare] La doppia protezione della password è sicura per l'autenticazione dell'amministratore?

score 4 · Accepted Answer

Esiste un algoritmo O (n) abbastanza semplice:

Lascia che pos sia una matrice in modo che se la persona al posto i vuole parlare come n -th, abbiamo una voce pos[i] = n . Dove inizia la numerazione dei posti è irrilevante. Sia i che n iniziano a contare con zero.

La differenza i - pos[i] è il posto in cui il giro dovrebbe iniziare per la persona al posto i da soddisfare. Contiamo le persone soddisfatte per posizione iniziale in una matrice satisfied . Possiamo quindi trovare il massimo di tale array, l'indice del massimo è il posto in cui dovrebbe iniziare il round per la massima soddisfazione.

Esempio Java:

int findBestStart(int[] pos) {
    // ask each seat where they'd like to start
    int[] satisfied = new int[pos.length];
    for (int i = 0; i < pos.length; i++) {
        int start = i - pos[i]
        if (start < 0) start += pos.length;
        satisfied[start]++;
    }

    // find where most would like to start
    int bestSeat = -1;
    int bestSatisfied = -1;
    for (int i = 0; i < satisfied.length; i++) {
        if (satisfied[i] > bestSatisfied) {
            bestSeat = i;
            bestSatisfied = satisfied[i];
        }
    }

    return bestSeat;
}