Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Sommario

1. Tre elementi della struttura dei dati

1.1 Operazioni sulle strutture dati

1.2 Struttura di memorizzazione della struttura dei dati

2. Tipo di dati, tipo di dati astratti

3. Algoritmo

3.1 Complessità temporale T(n)

3.2 Complessità spaziale

---

1. Tre elementi della struttura dei dati

1.1 Operazioni sulle strutture dati

Cioè aggiungere, eliminare, modificare e controllare

1.2 Struttura di memorizzazione della struttura dei dati

2. Tipo di dati, tipo di dati astratti

tipo di dati:

(1) Tipo atomico: bool, int...

(2) Tipo strutturale: classe, struttura...

Tipo di dati astratti (ADT):

Simile ai tipi di struttura, usersSoltantoÈ necessario conoscere la struttura dei datinomee le connessioni tra i loro dati (funzione) Potere

3. Algoritmo

3.1 Complessità temporale T(n)

Minore è la complessità temporale, migliore è l'algoritmo

(1). Regole operative

aggiunta:

Aggiunta di più elementiQuando , viene mantenuto solo il termine di ordine più alto (potenza).

T1(n) + T2(m) = T(max(n,m))

moltiplicazione:

T1 x T2 = O( f(n) xg(n))

(2). Confronti comuni per ordine di grandezza

In genere, è sufficiente ricordare i primi tre e gli ultimi tre -La coppia costante di potere si riferisce all'ordine 

3.2 Complessità spaziale

1 GB = 1024*1024*1024 byte equivale a circa 1 miliardo

1GB=1024MB 1MB=1024KB 1KB=1024 byte

In effetti, non è necessario conoscere il numero di byte memorizzati nei vari tipi di dati, basta memorizzarli direttamente come numeri. Dopotutto, alla fine, i coefficienti verranno omessi e trasformati in una formula di calcolo contenente n con un coefficiente di uno.

Nella funzione, comeparametroTutti i dati in arrivo lo sonoNon c'è bisognoviene conteggiato come parte della complessità dello spazio perché il numero di questi parametri è noto e può essere omesso (ad eccezione delle funzioni ricorsive)

Nella funzione, ciò che deve essere calcolato sono quelliIn una funzione, la dichiarazione produceVariabili.

speciale:

Nella funzione ricorsiva, ogni volta che i dati vengono passati, enon coprirànella sua posizione originale, ma conservatanuovo indirizzoPertanto, se si desidera determinare la complessità spaziale di una funzione ricorsiva, è necessario avere chiaro l'utilizzo della memoria dell'intero processo dal punto iniziale al punto finale della ricorsione.

Quando si tratta di funzioni ricorsive sugli array, in particolarevettoreDilunghezzaavviene con la ricorsioneModifica, quindi è spesso necessario utilizzareSomma di sequenze aritmetiche，