Teknologian jakaminen

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

1. Algoritmin tehokkuus

Saman algoritmiongelman suorittamiseen on monia tapoja ja menetelmiä. Lopullinen vaikutus on sama ja oikea, mutta tehokkuus voi olla erilainen.
Aivan kuten samasta paikasta lähdettäessä ja toiseen paikkaan saapuessa, paikanpäälle pääsee lentokoneilla, junilla, henkilöautoilla... mutta aika on erilainen ja myös taloudellinen.

1. Monimutkaisuuden käsite

Kun algoritmi on kirjoitettu suoritettavaan ohjelmaan, sen suorittaminen vaatii aika- ja tilaa (muisti)resursseja. Siksi algoritmin laatua mitataan yleensä kahdesta ulottuvuudesta: ajasta ja paikasta, eli ajan kompleksisuudesta ja tilan monimutkaisuudesta.
Aikamonimutkaisuus mittaa pääasiassa sitä, kuinka nopeasti algoritmi toimii, kun taas tilan monimutkaisuus mittaa pääasiassa algoritmin suorittamiseen tarvittavaa ylimääräistä tilaa.
Tietokoneiden kehittämisen alkuaikoina tietokoneilla oli hyvin pieni tallennuskapasiteetti. Joten välitämme paljon tilan monimutkaisuudesta. Tietokoneteollisuuden nopean kehityksen jälkeen tietokoneiden tallennuskapasiteetti on kuitenkin saavuttanut erittäin korkean tason. Joten nyt meidän ei enää tarvitse kiinnittää erityistä huomiota algoritmin avaruuden monimutkaisuuteen.

2. Monimutkaisuuden merkitys

Kun pelaan joitain pelejä, puhelimeni on erittäin kuuma, kun pelaan joitain pelejä, ja jotkut pelit eivät ole kuumia, jos pelaan niitä, mikä on erottamaton monimutkaisuudesta. Puhelimessani on yksinkertainen algoritmi ja se toimii nopeasti, mutta se toimii Algoritmi on monimutkainen, jotta aikaa kuluu vähemmän, täysi teho on otettava käyttöön, jotta se kuumenee.

2. Aika monimutkaisuus

Määritelmä: Tietojenkäsittelytieteessä algoritmin aikakompleksisuus on funktionaalinen kaava T(N), joka kuvaa kvantitatiivisesti algoritmin ajoaikaa. Aika monimutkaisuus mittaa ohjelman aikatehokkuutta, joten miksi et laske ohjelman ajoaikaa?

• Koska ohjelman ajoaika liittyy käännösympäristön ja käynnissä olevan koneen kokoonpanoon, esimerkiksi jos algoritmiohjelma käännetään vanhalla kääntäjällä tai käännetään uudella kääntäjällä, ajoaika on erilainen samalla koneella.
• Samalla algoritmiohjelmalla on eri ajoajat vanhalla matalakonfiguraatiokoneella ja uudella korkean konfiguraation koneella.
• Ja aikaa voidaan testata vasta ohjelman kirjoittamisen jälkeen, ei laskea ja arvioida teoreettisella ajattelulla ennen ohjelman kirjoittamista.

Tämän vuoksi algoritmin aikajakoa arvioitaessa ei huomioida algoritmin suoritusaikaa, vaan ainoastaan ​​suoritettujen käskyjen määrää.

Tapaus:

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

Havainnon kautta:
Func1:n suorittamien perustoimintojen lukumäärä:
T(N) = N²+ 2*N + 10

Käytännössä aika monimutkaisuutta laskettaessa emme laske ohjelman tarkkaa suoritusten määrää tämä), suoritusten tarkan lukumäärän laskemisella on vähän merkitystä, koska haluamme verrata vain algoritmiohjelman kasvutasoa laskettaessa aikamonimutkaisuutta, eli T(N):n eroa, kun N jatkaa kasvuaan ovat nähneet edellä, että vakioilla ja matalan kertaluvun termillä on vain vähän vaikutusta tuloksiin, kun N jatkaa kasvuaan, joten meidän tarvitsee vain laskea likimääräinen suoritusten määrä, jota ohjelma voi edustaa, jotta suuruusluokka kasvaisi yleensä käytetään Käytä Big O:n asymptoottista merkintää.

3. Tilan monimutkaisuus

Tilan monimutkaisuus on myös matemaattinen lauseke, joka on algoritmin ajon aikana väliaikaisesti varattu lisätila algoritmin tarpeiden vuoksi.
Tilan monimutkaisuus ei tarkoita kuinka monta tavua tilaa ohjelma vie, koska normaalioloissa kunkin objektin koko ei poikkea suuresti, joten tilan monimutkaisuus lasketaan muuttujien lukumäärän mukaan.
Tilan monimutkaisuuden laskentasäännöt ovat pohjimmiltaan samanlaisia ​​kuin käytännön monimutkaisuus, ja myös Big O -asymptoottista merkintää käytetään.
Huomaa: funktion ajon aikana tarvittava pinotila (parametrien, paikallisten muuttujien, joidenkin rekisteritietojen tallentaminen jne.) on määritetty käännöksen aikana, joten tilan monimutkaisuus määräytyy pääasiassa funktion ajon aikana käyttämän lisätilan perusteella. . Varma
Avaruus ei ole avaintekijä nykyisessä tietokonekehityksessä, mutta liiallista tuhlausta on vältettävä.

4. Big O:n asymptoottinen esitys

Big O -merkintä: Se on matemaattinen symboli, jota käytetään kuvaamaan funktioiden asymptoottista käyttäytymistä.
Säännöt siirtymiselle Big O:n asymptoottiseen merkintään:

• 1. Aikamonimutkaisuuden funktionaalisessa kaavassa T(N) vain korkeimman kertaluvun termit säilytetään ja alemman kertaluvun termit poistetaan, koska kun N jatkaa kasvuaan,
  Alemman asteen termien vaikutus tuloksiin pienenee ja pienenee, ja kun N on ääretön, ne voidaan jättää huomiotta.
• 2. Jos korkeimman kertaluvun termi on olemassa eikä se ole 1, poista tämän termin vakiokerroin, koska N:n kasvaessa tämä kerroin
  Vaikutus tuloksiin pienenee koko ajan, ja kun N on ääretön, se voidaan jättää huomiotta.
• 3. Jos T(N):ssä ei ole N:ään liittyviä kohteita vaan vain vakioyksiköitä, korvaa kaikki summaavat vakiot vakiolla 1.

Huonoin tapaus: ajojen enimmäismäärä (yläraja) mille tahansa syötekoolle
Keskimääräinen tapaus: odotettu ajojen määrä mille tahansa syötekoolle
Paras tapaus: ajojen vähimmäismäärä (alaraja) mille tahansa syöttökoolle
Käytännössä Big O:n asymptoottinen esitys keskittyy yleensä algoritmin ylärajaan, joka on huonoin toimintatilanne.

5. Laskennallisen monimutkaisuuden tapaukset

1. Laske Func1-funktion monimutkaisuus

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

aika monimutkaisuus:

Jätä pois kerran suoritettava koodi, kuten count=0, tämä koodi.
Säilytä sellaisten koodin suoritusten määrä, joilla on suuri vaikutus ajoaikaan
Ensimmäisen silmukan suoritusten määrä on N:n kaksoissilmukan suoritusN
Toinen silmukka on kerros silmukan suorituskertoja 2N
Kolmas sykli on 10 kertaa
Suoritusten lukumäärän summa on T(N)=N²+2*N+10
Big O edustaa ajan monimutkaisuutta, hylkää pieni vaikutus ja ota raja
PÄÄLLIJ)

Avaruuden monimutkaisuus:

Func1 pätee avaruuden kokoon Esimerkiksi int count = 0, se pätee int-tyypin tilan kokoon M=10, se koskee myös int-tyypin tilaa.
Näitä kahta tilaa käytetään myös silmukassa ilman lisäsovellustilaa.
Sovellustilan koko on vakio
Big O:lla ilmaistu tilan monimutkaisuus on:
O(1)

2. Laske Fun2:n aikamonimutkaisuus

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

aika monimutkaisuus:

Koodin suorituskertojen määrä on suurempi kuin ensimmäinen silmukka, joka on N*2.
Toinen silmukka kulkee 10 kertaa
Käytä suurta O:ta kuvaamaan aika monimutkaisuutta. Suurin vaikutus on 2*N. Edellinen kerroin on jätetty pois.
PÄÄLLÄ)

3. Laske Func3:n aikamonimutkaisuus

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

aika monimutkaisuus

On kaksi tuntematonta, ja suurempi vaikutus on kahdella silmukalla
Ensimmäinen silmukka kulkee M kertaa
Toinen silmukka kulkee N kertaa
Sen pitäisi olla tuntematon, en ole varma, kumpi on suurempi ja kumpi pienempi.
O(M+N)

4. Laske Func4:n aikamonimutkaisuus

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

aika monimutkaisuus:

Suurin vaikutus tässä on sykli
Silmukan suorituskertojen määrä on 100
on kiinteä vakio
O(1)

5. Laske strchr:n aikamonimutkaisuus

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

Tämän toiminnon suorittama toiminto on löytää taulukon merkin alaindeksi.
Juoksujen määrä täällä on epävarma
On mahdollista löytää F(N)=1 yhdellä kertaa
Keskeltä on mahdollista löytää F(N)=N/2
Se saattaa löytyä lopusta tai palautetaan NULL, jos sitä ei löydy, F(N)=N
Big O ottaa pahimman skenaarion:
Aika monimutkaisuus on O(N)

6. Laske Func5:n aikamonimutkaisuus

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

Tämä ajojen määrä liittyy n:n kokoon, mutta se ei tee silmukkaa n kertaa. Sen pitäisi johtua siitä, että silmukkamuuttuja kerrotaan 2:lla silmukan aikana ja silmukka hyppää ulos nopeasti kymmenen kertaa. silmukkamuuttujan cnt arvo saavuttaa 1024.
Jos syklien lukumäärä on x, niin 2^x=n
x=kirjautuminen
Joten aika monimutkaisuus on: O (longn)

7. Laske BubbleSorin monimutkaisuus

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

Tämä toiminto päättää kuplan nousevan lajittelun
Tässä on silmukka. Tämä silmukka on kaksitasoinen sisäkkäinen silmukka.
Silmukoiden lukumäärää ei ole määritelty
Pahin tapaus on, että ulompi silmukka kulkee n kertaa
Sitten sisäsilmukka kulkee (n-1)+(n-2)+(n-3)+……+2+1+0
on aritmeettinen sarja ja summa on:

Aika monimutkaisuus on: O(N)

Avaruuden monimutkaisuus:

Lisäsovellustilaa ei ole, ja käytetty tila on vakio.
O(1)

8. Faktoriaalisen rekursion laskennan monimutkaisuus Fac

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

aika monimutkaisuus:

Toistettu N kertaa
Joten aika monimutkaisuus on: O(N)

Avaruuden monimutkaisuus:

Joka kerta kun toistat, sinun on haettava tilaa.
Toistettiin N kertaa ja sovellettiin N kertaa tilaa.
Avaruuden monimutkaisuus on: O(N)