Dovrei considerare memmove() O (n) o O (1)?

questa può essere una domanda stupida, ma voglio calcolare la complessità di uno dei miei algoritmi e non sono sicuro di quale complessità considerare per la funzione memmove().Dovrei considerare memmove() O (n) o O (1)?

Potete aiutare/spiegare?

void * memmove (void * destination, const void * source, size_t num);

Così è la complessità O (num) o O (1). Suppongo che sia O (num), ma non sono sicuro perché mi manca per ora la comprensione di cosa sta succedendo sotto il cofano.

fonte

2010-04-25 Andrei Ciobanu

La risposta corretta è probabilmente che dipende dall'implementazione. Puoi immaginare un sistema insolito in cui la memoria è in realtà un grafico complesso o una lista collegata. In ogni sistema reale sono consapevole che è proporzionale a num. –

Poiché il tempo di esecuzione di memmove aumenta in proporzionalità diretta con il numero di byte che è necessario spostare, è O (n).

fonte

2010-04-25 21:20:30

O (n) è la corretta complessità asintotica, ma non credo che userei il termine "proporzionalità diretta" in questo contesto, anche per qualcosa di semplice come "memmove". Considerare n = 4 contro n = 1 byte su un'architettura a 32 bit: il caso n = 1 potrebbe essere effettivamente l'operazione più costosa! –

È 'O (n)' dove 'n' è il conteggio passato a' memmove() '- ma che potrebbe non essere proporzionale al' n' che stai usando per caratterizzare il tuo algoritmo. – caf

Che cosa si sta applicando l'operazione memmove() a - elementi selezionati nell'algoritmo o tutti? Stai applicando memmove() a elementi più di una volta?

Queste sono le cose che contano per la complessità dell'algoritmo.

Questa risposta può essere differente che la complessità di memmove() stessa per quanto riguarda le matrici di char elementi che memmove() tratta (per il quale memmove() è un O (n)).

fonte

2010-04-26 07:57:32

Dovrei considerare memmove() O (n) o O (1)?

risposta

Problemi correlati