Teknologian jakaminen

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

Esipuhe

Jos haluat tietää, mitä tila/aika monimutkaisuus on, sinun on tiedettävä, mikä tietorakenne on.

Tämä voidaan ymmärtää kahdella tasolla. Dataa on kaikkialla elämässämme, kuten kansainväliset tapahtumat, jotka ovat kuumia aiheita Douyinissa, Yongzhengin panssarin poisto jne. Käyttäjämme näkevät tiedot, jotka Douyin tallentaa taustapalvelimelle. Mutta näillä tiedoilla kaikilla on yksi ominaisuus, toisin sanoen ne ovat kaikki Douyinin suositulla hakuluettelolla, ja tämä luettelo on rakennettu varmistamaan, että tiedot ovat kiinteässä paikassa käyttäjien selaamista varten.

Lisäksi tietorakenteissa algoritmit ovat erottamattomia. No, kuten juuri sanoimme, tietorakenne tallentaa tiedot säännöllisesti rakenteeseen, joten kuinka saada tietoja tehokkaasti rakenteesta, on algoritmi.

aika monimutkaisuus

Algoritmeilla on aika- ja tilamonimutkaisuutta. Koska tietokoneiden muisti kasvaa koko ajan, ajan monimutkaisuus on tärkeämpää kuin tilan monimutkaisuus.Ymmärrämme siis ensin ajan monimutkaisuus

konsepti

Aika monimutkaisuus, tärkein sana on aika, aika tarkoittaa tässä aikaa, jolloin ohjelma on käynnissä. Jos aika monimutkaisuus on pienempi, niin algoritmi on osoittautunut paremmaksi.Aikamonimutkaisuuslaskelma ilmaistaan ​​funktionaalisella kaavalla T(N)

Joten miksi emme laske etukäteen tämän ohjelman aikamonimutkaisuutta ja kirjoita optimaalisen ratkaisun koodia? Tähän liittyy tietokoneongelmia.

1. Koska ohjelman ajoaika liittyy esimerkiksi käännösympäristöön ja käynnissä olevan koneen kokoonpanoon, algoritmiohjelma käyttää vanhaa kääntäjää
   Kääntämisessä uudella kääntäjällä ja kääntämisellä uudella kääntäjällä on eri ajoajat samassa koneessa.
2. Samalla algoritmiohjelmalla on eri ajoajat vanhalla matalakonfiguraatiokoneella ja uudella korkean konfiguraation koneella.
3. Ja aikaa voidaan testata vasta ohjelman kirjoittamisen jälkeen, ei laskea ja arvioida teoreettisella ajattelulla ennen ohjelman kirjoittamista.

Katsotaanpa koodinpätkä:

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

Jos tarkastelet tätä koodia laskun suoritusten lukumäärän perusteella, sen pitäisi olla:
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10 210
• N = 1000 T(N) = 1002010

Tällä hetkellä joku sanoi, eikö tuota int count=0 lasketa;

Tässä aliarvioimme tietokoneemme liikaa. Tietokoneemme suoritin voi suorittaa satoja miljoonia kertoja sekunnissa. Siksi laskemamme aikamonimutkaisuus ei ole tarkka, se on vain karkea arvio. Tällä hetkellä käytämme sitä edustamaan uutta symbolia.

Big O:n asymptoottinen merkintä

Big O -merkintä: Se on matemaattinen symboli, jota käytetään kuvaamaan funktion asymptoottista käyttäytymistä. Sitä käytetään tässä edustamaan arvioitua aikamonimutkaisuutta.

Joten lasketaanko se edelleen T(N):ksi, jos on, meidän ei tarvitse käyttää toista symbolia sen esittämiseen? Tämä sisältää O-laskennan säännöt:

1. Aikamonimutkaisuuden funktionaalisessa kaavassa T(N) vain korkeimman kertaluvun termit säilytetään ja alemman kertaluvun termit poistetaan, koska N:n kasvaessa alemman kertaluvun termien vaikutus tulokseen pienenee ja pienenee. Kun N on ääretön, se voidaan jättää huomiotta.
2. Jos korkein kertaluku on olemassa ja se ei ole 1, poista tämän termin vakiokerroin, koska N:n kasvaessa tällä kertoimella on yhä vähemmän vaikutusta tulokseen. Kun N on ääretön, se voidaan jättää huomiotta.
3. Jos T(N):ssä ei ole N:ään liittyviä kohteita vaan vain vakioita, korvaa kaikki summaavat vakiot vakiolla 1.

Katso sitten yllä olevaa T(N)=N^ 2 + 2 ∗ N + 10. Korkein kertaluku tässä on N2, joten poistamalla muut matalat arvot monimutkaisuus on (ON^2)

Pienen mittakaavan helikopteri

// 计算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

Tässä T(N)=M+N, lasketaan sitten taas O(N) tässä ovat molemmat samaa luokkaa, joten ne eivät noudata ensimmäistä sääntöä eivätkä vastaa toista ja kolmatta sääntöä. , joten o(N+M), sitten joku kysyi, mitä jos N on suurempi kuin M, pitäisikö sen olla O(N) Kysymys kuuluu, mistä tiedät, että N on suurempi kuin M? Entä jos M on suurempi kuin N, joten pysymme täällä vain varmuuden vuoksi.

// 计算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

Tässä etsimme hahmon asemaa str. Lisään tähän tietopisteen:

• O-laskelmamme on yleensä algoritmin pahimman tapauksen monimutkaisuus.
  Tässä se voidaan jakaa kolmeen monimutkaisuustasoon:
  1. Paras tapaus
  Voit etsiä merkkijonon ensimmäisestä sijainnista seuraavasti:
  F (N) = 1, kompleksisuus on o(1)

2. Keskimääräinen tilanne:
Löytääksesi merkin merkkijonon keskeltä, toimi seuraavasti:
F (N) = N/2, O (N/2)

3. Pahin skenaario
Etsi merkkijonon viimeisestä sijainnista seuraavalla tavalla:
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

Pahimmassa tapauksessa, koska korkea järjestys säilyy ja n/2 poistetaan (ensimmäinen kohde) ja kerroin (toinen kohde) jätetään huomiotta, se on ON^2

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

Kun n = 2, suoritusten määrä on 1
Kun n = 4, suoritusten määrä on 2
Kun n = 16, suorituksia on 4
Olettaen, että suoritusten määrä on x, niin 2
x = n
Siksi suoritusten määrä: x = log n
Siksi: func5:n pahimman mahdollisen ajan monimutkaisuus on:
O(log2 ^n)

Eri kirjoissa on erilaisia ​​ilmaisumenetelmiä. Yllä olevat kirjoitustavat eivät ole kovin erilaisia

tilan monimutkaisuus

Avaruuden monimutkaisuudesta tulee huomioida, että sen laskentaesitystä edustaa myös O, ja sen säännöt noudattavat samoja kolmea sääntöä kuin aikamonimutkaisuus.

Ilmoitus

Toiminnon ajon aikana tarvittava pinotila (parametrien, paikallisten muuttujien, jonkin verran rekisteritietoja jne.) on määritetty kääntämisen aikana, joten tilan monimutkaisuus määräytyy pääasiassa funktion ajon aikana hakeman lisätilan perusteella. .

esimerkki 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

Funktiopinon kehys on määritetty käännöksen aikana.
Sinun tarvitsee vain kiinnittää huomiota toiminnon ajon aikana vaatimaan lisätilaan.
Lisäsovellustilaa BubbleSortille on
Paikallisia muuttujia, kuten vaihtoa, on rajoitettu määrä, joka käyttää jatkuvasti ylimääräistä tilaa.
Joten avaruuden kompleksisuus on O(1)