Condivisione della tecnologia

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

1. Efficienza dell'algoritmo

Esistono molti modi e metodi per completare lo stesso problema dell'algoritmo. Il risultato finale è lo stesso e corretto, ma l'efficienza può variare.
Proprio come partire dallo stesso posto e arrivare in un altro posto, i modi per raggiungere il posto includono aerei, treni, auto private... ma il tempo impiegato è diverso e anche l'economia è diversa.

1. Il concetto di complessità

Dopo che l'algoritmo è stato scritto in un programma eseguibile, richiede risorse di tempo e spazio (memoria) per essere eseguito. Pertanto, la qualità di un algoritmo viene generalmente misurata da due dimensioni: tempo e spazio, ovvero complessità temporale e complessità spaziale.
La complessità temporale misura principalmente la velocità di esecuzione di un algoritmo, mentre la complessità spaziale misura principalmente lo spazio aggiuntivo richiesto per eseguire un algoritmo.
Agli albori dello sviluppo dei computer, i computer avevano una capacità di archiviazione molto ridotta. Quindi ci preoccupiamo molto della complessità dello spazio. Tuttavia, dopo il rapido sviluppo dell’industria informatica, la capacità di archiviazione dei computer ha raggiunto un livello molto elevato. Quindi ora non è più necessario prestare particolare attenzione alla complessità spaziale di un algoritmo.

2. L'importanza della complessità

Quando gioco ad alcuni giochi, il mio telefono si surriscalda molto mentre gioco, e alcuni giochi non si surriscaldano se li gioco, il che è inseparabile dalla complessità. Il mio telefono esegue un algoritmo semplice e funziona velocemente, ma lo fa è complicato da eseguire Algoritmo, per garantire che il tempo venga utilizzato meno, è necessario abilitare la piena potenza, quindi si surriscalderà.

2. Complessità temporale

Definizione: in informatica, la complessità temporale di un algoritmo è una formula funzionale T(N), che descrive quantitativamente il tempo di esecuzione dell'algoritmo. La complessità temporale misura l'efficienza temporale di un programma, quindi perché non calcolare il tempo di esecuzione del programma?

• Poiché il tempo di esecuzione del programma è correlato alla configurazione dell'ambiente di compilazione e della macchina in esecuzione, ad esempio, se un programma algoritmo viene compilato con un vecchio compilatore o compilato con un nuovo compilatore, il tempo di esecuzione sarà diverso sulla stessa macchina.
• Lo stesso programma algoritmo ha tempi di esecuzione diversi utilizzando una vecchia macchina a bassa configurazione e una nuova macchina ad alta configurazione.
• 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.

Pertanto, nel valutare il grado di assegnazione temporale di un algoritmo, non viene considerato il tempo di esecuzione dell'algoritmo, ma solo il numero di istruzioni eseguite.

Caso:

// 请计算⼀下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

Attraverso l'osservazione:
Numero di operazioni di base eseguite da Func1:
T(N)=N²+ 2*N + 10

In pratica, quando calcoliamo la complessità temporale, non calcoliamo il numero esatto di esecuzioni del programma. Calcolare il numero esatto di esecuzioni è ancora molto problematico (frasi diverse del codice del programma avranno numeri diversi di istruzioni compilate (come questo), calcolare il numero esatto di esecuzioni ha poca importanza, perché vogliamo solo confrontare il livello di crescita del programma dell'algoritmo nel calcolare la complessità temporale, cioè la differenza di T(N) quando N continua ad aumentare We abbiamo visto sopra che le costanti e i termini di ordine inferiore hanno un impatto minimo sui risultati quando N continua a crescere, quindi dobbiamo solo calcolare il numero approssimativo di esecuzioni che il programma può rappresentare per aumentare l'ordine di grandezza dell'espressione di complessità solitamente usato Usa la notazione asintotica di Big O.

3. Complessità spaziale

Anche la complessità dello spazio è un'espressione matematica, ovvero lo spazio aggiuntivo temporaneamente allocato a causa delle esigenze dell'algoritmo durante il funzionamento di un algoritmo.
La complessità dello spazio non è la quantità di byte di spazio occupati dal programma. Poiché in circostanze normali, la dimensione di ciascun oggetto non differisce notevolmente, la complessità dello spazio viene calcolata in base al numero di variabili.
Le regole di calcolo della complessità spaziale sono sostanzialmente simili alla complessità pratica e viene utilizzata anche la notazione asintotica Big O.
Nota: 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 durante il runtime . Sicuro
Lo spazio non è una considerazione chiave nell’attuale sviluppo dei computer, ma gli sprechi eccessivi devono essere evitati.

4. Rappresentazione asintotica di Big O

Notazione Big O: è un simbolo matematico utilizzato per descrivere il comportamento asintotico delle funzioni.
Regole per passare alla notazione asintotica Big O:

• 1. Nella formula funzionale della complessità temporale T(N), vengono mantenuti solo i termini di ordine più elevato e quelli di ordine inferiore vengono rimossi, perché quando N continua ad aumentare,
  L'impatto dei termini di ordine inferiore sui risultati diventa sempre più piccolo e quando N è infinito possono essere ignorati.
• 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 ad aumentare, questo coefficiente
  L'impatto sui risultati diventa sempre più piccolo e 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.

Caso peggiore: numero massimo di esecuzioni (limite superiore) per qualsiasi dimensione di input
Caso medio: numero previsto di esecuzioni per qualsiasi dimensione di input
Caso migliore: numero minimo di esecuzioni (limite inferiore) per qualsiasi dimensione di input
In pratica, la rappresentazione asintotica di Big O si concentra generalmente sul limite superiore dell’algoritmo, che rappresenta la peggiore situazione operativa.

5. Casi di complessità computazionale

1. Calcola la complessità della funzione Func1

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

complessità temporale:

Ometti il ​​codice che viene eseguito una volta, ad esempio count=0, questo codice.
Mantieni il numero di esecuzioni di codice che hanno un grande impatto sul tempo di esecuzione
Il numero di esecuzioni del primo ciclo è un'esecuzione di doppio ciclo di NN
Il secondo ciclo è uno strato di tempi di esecuzione del ciclo 2N
Il terzo ciclo è di 10 volte
La somma del numero di esecuzioni è T(N)=N²+2*N+10
La O grande rappresenta la complessità del tempo, scarta il piccolo impatto e prendi il limite
SU²)

Complessità spaziale:

La funzione Func1 si applica alla dimensione dello spazio. Ad esempio, int count = 0, si applica alla dimensione dello spazio del tipo int M=10, si applica anche allo spazio del tipo int.
Questi due spazi vengono utilizzati anche nel loop senza spazio applicativo aggiuntivo.
La dimensione dello spazio dell'applicazione è costante
La complessità spaziale espressa in Big O è:
L'(1)

2. Calcolare la complessità temporale di Fun2

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	} 
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

complessità temporale:

Il numero di volte in cui il codice viene eseguito è maggiore del primo ciclo, ovvero N*2.
Il secondo ciclo viene eseguito 10 volte
Utilizza la O grande per rappresentare la complessità temporale. L'impatto maggiore è 2*N. Il termine del coefficiente precedente viene omesso:
SU)

3. Calcolare la complessità temporale di 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

complessità temporale

Ci sono due incognite e l’impatto maggiore si ha sui due circuiti
Il primo ciclo viene eseguito M volte
Il secondo ciclo viene eseguito N volte
Dovrebbe essere un numero sconosciuto. Non sono sicuro di quale sia più grande e quale sia più piccolo, non lo ometterò.
O(M+N)

4. Calcolare la complessità temporale di Func4

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9

complessità temporale:

L’impatto maggiore qui è un ciclo
Il numero di volte in cui il ciclo viene eseguito è 100
è una costante fissa
L'(1)

5. Calcola la complessità temporale di strchr

const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	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

La funzione svolta da questa funzione è trovare l'indice di un carattere in un array.
Il numero di corse qui è incerto
È possibile trovare F(N)=1 in un colpo solo
Nel mezzo è possibile trovare F(N)=N/2
Può essere trovato alla fine, oppure viene restituito NULL se non trovato, F(N)=N
Big O prende lo scenario peggiore:
La complessità temporale è O(N)

6. Calcolare la complessità temporale di Func5

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

Questo numero di esecuzioni è correlato alla dimensione di n, ma non esegue il ciclo n volte. Dovrebbe essere perché la variabile del ciclo verrà moltiplicata per 2 durante il ciclo e il ciclo uscirà rapidamente dopo essere stato eseguito dieci volte il valore della variabile del ciclo cnt raggiungerà 1024.
Supponendo che il numero di cicli sia x, allora 2^X=non
x=logn
Quindi la complessità temporale è: O(longn)

7. Calcola la complessità di BubbleSor

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

Questa funzione completa l'ordinamento ascendente delle bolle
C'è un ciclo qui. Questo ciclo è un ciclo nidificato a due livelli.
Il numero di loop non è definito
Lo scenario peggiore è che il ciclo esterno venga eseguito n volte
Quindi il ciclo interno verrà eseguito (n-1)+(n-2)+(n-3)+……+2+1+0
è una sequenza aritmetica e la somma è:

La complessità temporale è: O(N)

Complessità spaziale:

Non c'è spazio aggiuntivo per l'applicazione e lo spazio applicato è costante.
L'(1)

8. La complessità del calcolo della ricorsione fattoriale Fac

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6

complessità temporale:

Ricorso N volte
Quindi la complessità temporale è: O(N)

Complessità spaziale:

Ogni volta che ricorsi, devi fare domanda per il posto.
Ricorso N volte e richiesto N volte di spazio.
La complessità dello spazio è: O(N)