Qual è una definizione formale per un passo dell'algoritmo?

Naviga le tue risposte
0

Considera il seguente codice per trovare l'elemento minimo di th di un array: 

FindKthMin(A[], k)
{
    A = Sort(A);
    return A[k];
}

Potrebbe essere un algoritmo senza specificare i dettagli di sort ?

Possiamo dire che l'algoritmo non ha significato senza specificare il set di istruzioni (macchina di destinazione e il suo set di istruzioni di base)

Ad esempio in BubbleSort dovremmo specificare i dettagli di Swap(..) o Add(..) ? Voglio dire quali sono quelle istruzioni atomiche che ci impedirebbero di andare oltre?

O che cos'è una definizione formale per un passo dell'algoritmo? Esiste una definizione matematica generale per esso (come le funzioni o qualcosa del genere)?

    
posta Ahmad 19.02.2015 - 06:43
fonte

2 risposte

4

Non ha senso parlare della complessità del passo di un algoritmo senza definire cosa sia un "passo" per primo. La complessità algoritmica è sempre relativa a un modello di calcolo, che si tratti di transizioni di una macchina di Turing, riduzioni del calcolo λ, istruzioni di una macchina ad accesso casuale o il numero di confronti quando si parla di confronto basato ordina come bubble sort, quick sort, merge sort, tim sort ecc.

Nota anche che gli algoritmi non hanno necessariamente bisogno di avere "passi". Gli algoritmi analogici sono continui, non hanno passaggi.

    
risposta data 19.02.2015 - 07:06
fonte
2

Quando si definisce o si parla di complessità algoritmica, si ha sempre in mente una macchina (implicita) di destinazione astratta (ad es. RAM machine , macchina SECD , ecc.). Quindi i passaggi elementari sono quelli di quella macchina target.

L'ordinamento a bolle è O (n 2 ) solo con l'ipotesi che i confronti siano tempo costante. Se immagini di ordinare bignums probabilmente non è più il caso (un confronto individuale è quindi probabilmente proporzionale alla dimensione di i numeri confrontati, cioè al loro logaritmo)

    
risposta data 19.02.2015 - 06:55
fonte

Leggi altre domande sui tag

Capitalizzazione dei metodi personalizzati in un progetto basato su SDK [chiuso] Quali sono i vantaggi di un ambiente a 3 stadi per lo sviluppo SAP / BI?