Condivisione della tecnologia

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

Prefazione

Se vuoi sapere cos'è la complessità spazio/temporale, devi sapere cos'è una struttura dati.

Ciò può essere compreso a due livelli. I dati esistono ovunque nella nostra vita, come gli eventi internazionali che sono temi caldi su Douyin, la rimozione dell'armatura di Yongzheng, ecc. Ciò che i nostri utenti possono vedere sono i dati che Douyin archivia nel server backend. Ma questi dati hanno tutti una caratteristica, ovvero sono tutti nell’elenco di ricerca caldo di Douyin e questo elenco è strutturato per garantire che i dati si trovino in una posizione fissa affinché gli utenti possano sfogliarli.

Inoltre, con le strutture dati, gli algoritmi sono inseparabili. Bene, come abbiamo appena detto, una struttura dati memorizza regolarmente i dati in una struttura, quindi come accedere in modo efficiente ai dati dalla struttura è un algoritmo.

complessità temporale

Con gli algoritmi, c’è complessità temporale e complessità spaziale. Poiché la memoria dei computer diventa sempre più grande, la complessità temporale è più importante della complessità spaziale.Quindi comprendiamo innanzitutto la complessità temporale

concetto

Complessità temporale, la parola più importante è tempo, il tempo qui si riferisce al tempo in cui un programma è in esecuzione. Se la complessità temporale è inferiore, l'algoritmo risulta essere migliore.Il calcolo della complessità temporale è espresso dalla formula funzionale T(N)

Allora perché non calcoliamo in anticipo la complessità temporale di questo programma e scriviamo il codice per la soluzione ottimale? Ciò comporta problemi informatici.

1. Poiché il tempo di esecuzione del programma è correlato, ad esempio, all'ambiente di compilazione e alla configurazione della macchina in esecuzione, un programma con algoritmo utilizza un vecchio compilatore
   La compilazione con un nuovo compilatore e la compilazione con un nuovo compilatore hanno tempi di esecuzione diversi sulla stessa macchina.
2. Lo stesso programma algoritmo ha tempi di esecuzione diversi utilizzando una vecchia macchina a bassa configurazione e una nuova macchina ad alta configurazione.
3. E il tempo può essere testato solo dopo che il programma è stato scritto, non calcolato e valutato attraverso il pensiero teorico prima di scrivere il programma.

Diamo un'occhiata a un pezzo di codice:

// 请计算⼀下Func1中count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Se guardi questo codice in base al numero di esecuzioni di count, dovrebbe essere:
N(N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

In questo momento, qualcuno ha detto, int count=0 non conta;

Qui sottovalutiamo troppo il nostro computer. La CPU del nostro computer può eseguire centinaia di milioni di volte al secondo. Naturalmente, questo piccolo tempo può essere ignorato. Pertanto, la complessità temporale che abbiamo calcolato non è accurata, è solo una stima approssimativa. Al momento utilizziamo un nuovo simbolo per rappresentarla.

Notazione asintotica di Big O

Notazione Big O: è un simbolo matematico utilizzato per descrivere il comportamento asintotico di una funzione; qui viene utilizzato per rappresentare la complessità temporale stimata.

Quindi conta ancora come T(N) in questo caso? Se è così, non abbiamo bisogno di usare un altro simbolo per rappresentarlo. Ciò implica le regole per il conteggio di O:

1. Nella formula funzionale della complessità temporale T(N), vengono mantenuti solo i termini di ordine più alto e quelli di ordine più basso vengono rimossi, perché quando N continua ad aumentare, l'impatto dei termini di ordine più basso sul risultato diventa sempre più piccolo. Quando N è infinito, può essere ignorato.
2. Se il termine di ordine più alto esiste e non è 1, rimuovi il coefficiente costante di questo termine, perché man mano che N continua a crescere, questo coefficiente avrà sempre meno influenza sul risultato. Quando N è infinito, può essere ignorato.
3. Se in T(N) non sono presenti elementi correlati a N ma solo elementi costanti, sostituire tutte le costanti aggiuntive con la costante 1.

Quindi guarda quanto sopra T(N)=N^ 2 + 2 ∗ N + 10. L'ordine più alto qui è N2, quindi rimuovendo altri ordini bassi, la complessità è (ON^2)

Chopper di piccole dimensioni

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Qui T(N)=M+N, quindi calcoliamo di nuovo O(N). Qui M e N sono entrambi dello stesso ordine, quindi non soddisfano la prima regola e non corrispondono alla seconda e alla terza regola. , quindi o(N+M), poi qualcuno ha chiesto, e se N è maggiore di M, dovrebbe essere O(N). La domanda qui è: come fai a sapere che N è maggiore di M? E se M fosse più grande di N, quindi restiamo qui solo per sicurezza.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Qui stiamo cercando la posizione del personaggio in str. Qui aggiungerò un punto di conoscenza:

• Il nostro calcolo O è generalmente la complessità del caso peggiore di un algoritmo.
  Qui può essere suddiviso in tre livelli di complessità:
  1. Scenario migliore
  Per trovare il carattere nella prima posizione della stringa, quindi:
  F (N) = 1, la complessità è o(1)

2. Situazione media:
Per trovare il carattere al centro della stringa, quindi:
F(N) = N/2,O(N/2)

3. Scenario peggiore
Per trovare il carattere nell'ultima posizione della stringa, quindi:
F(N) = N,O(N)

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Nel peggiore dei casi, poiché viene mantenuto l'ordine più alto e viene rimosso n/2 (il primo elemento) e il coefficiente (il secondo elemento) viene ignorato, è ON^2

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

Quando n=2, il numero di esecuzioni è 1
Quando n=4, il numero di esecuzioni è 2
Quando n=16, il numero di esecuzioni è 4
Supponendo che il numero di esecuzioni sia x, allora 2
x = n
Pertanto il numero di esecuzioni: x = log n
Pertanto: la complessità temporale del caso peggiore di func5 è:
O(log2 ^n)

Libri diversi hanno metodi di espressione diversi. I metodi di scrittura sopra indicati non sono molto diversi. Si consiglia di utilizzare il log n

complessità spaziale

Ciò che va notato riguardo alla complessità dello spazio è che anche la sua rappresentazione nel calcolo è rappresentata da O, e le sue regole seguono le stesse tre regole della complessità del tempo.

Avviso

Lo spazio dello stack richiesto quando la funzione è in esecuzione (memorizzazione di parametri, variabili locali, alcune informazioni di registro, ecc.) è stato determinato durante la compilazione, quindi la complessità dello spazio è determinata principalmente dallo spazio aggiuntivo esplicitamente richiesto dalla funzione quando è in esecuzione .

Esempio 1:

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Il frame dello stack delle funzioni è stato determinato durante la compilazione.
Bisogna solo prestare attenzione allo spazio aggiuntivo richiesto dalla funzione durante il runtime.
Lo spazio applicativo aggiuntivo per BubbleSort è
Esiste un numero limitato di variabili locali come Exchange, che utilizza una quantità costante di spazio extra.
Quindi la complessità dello spazio è O(1)