strutture dati in c

[Bloody3000]

devo implementare una somma e sottrazione binaria in c con i bit dati da input da tastiera.
Visto che devo stringere il tempo di esecuzione e la memoria allocata (anche se le due cose sono inversamente proporzionali....) pensavo ad un array da riallocare dinamicamente man mano che la cifra diventa maggiore, "allungandolo" ogni volta di un tot fisso.
Esistono strutture migliori? Liste? Alberi non direi ma non si sa mai...... HELP ME

[infinitejustice]

Originariamente inviato da Bloody3000
tempo di esecuzione e la memoria allocata (anche se le due cose sono inversamente proporzionali....)

nn sono direttamente proporzionali?

[internet]

Non esiste una regola specifica di proporzionalità tra tempo di esecuzione e consumo di memoria.

Ma spesso aumentando il consumo di memoria si abbassa asintoticamente il tempo di esecuzione.

Esempi.

Tabella ad accesso diretto:
tempo di esecuzione per la ricerca: O(1)
memoria: bisogna allocarne tanta da contenere tutto l'universo U di tutte le possibili chiavi da inserire. O(U)

Tabella hash:
tempo di esecuzione per la ricerca:
con liste: O(1+a)
con indirizzamento apero: O((1/a)*ln(1/(1-a))
memoria: proporzionale al numero di chiavi K memorizzate e non a tutto l'universo U delle chiavi ammissibili. O(K)

Alberi binari:
tempo di esecuzione per le operazioni: O(log(n))
memoria: proporzionale al numero di elementi nell'albero.

Liste:
tempo di esecuzione: O(log(n))
memoria: proporzionale al numero di elementi nell'albero.

Programmazione dinamica:
es: Prodotto di una sequenza di matrici, con il minor numero di moltiplicazioni scalari.
tempo di esecuzione, parentesizzazione ottima : O(m^3) (m = numero di matrici)
memoria per il calcolo della parentesizzazione ottima : O(m^2).

Senza programmazione dinamica si risparmia il consumo di memoria pari a O(m^2), ma il tempo di esecuzione diventa esponenziale O(4^m)
, perchè è necessario ricercare tutte le parentesizzazioni possibili.

L'idea è sfruttare qualche forma caching per far diminiuire il tempo di esecuzione, accettando il compromesso di un cosumo maggiore di memoria.