Kas yra mano funkcijos laiko sudėtingumas?

Pradėdamas mokytis sudėtingumo, kovoju su šiuo:

 void what(int n) { int i; for (i = 1; i <= n; i++) { int x = n; while (x > 0) x -= i; } } 

Na, pirmoji kilpa aiškiai O(n) . Pirmasis iteravimas yra O(n) , antrasis yra O(n/2) .. ir, manau, log(n) kartus? Tai reiškia O(n) * O(log(n)) = O(n * log(n)) complexity . Ar aš teisingai suprantu?

Redaguoti: (ne dviem egzemplioriais) Žinau, kas yra Big O.

84
11 февр. nustatė Ilan Aizelman WS 11 vasaris 2016-02-11 00:20 '16 at 0:20 2016-02-11 00:20
@ 4 atsakymai

Išorinė kilpa vykdoma n kartus.

Kiekvienai iteracijai vidinės kilpos atliekamos n / i kartus.

Bendras skaičiavimų skaičius:

 n + n/2 + n/3 + ... + n/n 

Asimptotiniu būdu (ignoruojant sveiko skaičiaus aritmetinį apvalinimą), tai supaprastinama kaip

 n * (1 + 1/2 + 1/3 + ... + 1/n) 

Ši serija susilieja su n * log(n) .

Todėl, kaip tikėjotės , sudėtingumas yra O (N.log (N)) .

101
11 февр. atsakymas pateikiamas chqrlie 11 vasario mėn. 2016-02-11 00:34 '16 at 0:34 2016-02-11 00:34

Pirmoji vidinė kilpa vykdoma n kartų, o antroji vidinė kilpa vykdoma n/2 kartus, o trečioji vidinė kilpa vykdoma n/3 kartus.

Taigi n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n) .

Tai n padauginama iš harmoninių eilučių sumos, neturinčios geros uždaros formos. Tačiau, kaip parodyta čia , tai yra O(log(n)) . Taigi, paprastai algoritmas O(n log(n))

30
atsakymą pateikė Eugene Sh. Vasario 11 d 2016-02-11 00:33 '16 at 0:33 2016-02-11 00:33

Arba naudokite kintamąjį pakeitimą y = n - x , po to sekite Sigma žymėjimą, norėdami analizuoti vidinės kilpos iteracijų skaičių, while algoritmas.

2019

11 февр. Atsakymas dfri 11 vasaris. 2016-02-11 17:36 '16 at 17:36 pm 2016-02-11 17:36

Bandykite tai atlikti atlikdami bandymus ir grafiką. Log2 vs log2 linija atrodo gana linijinė. Kažkas tarp daugiau nei linijinio O (n) ir mažiau O (n * log (n)). Nupieškite savo išvadą.

[keisti]

Naudojant formulės matematinius darinius, apskaičiuotas O () yra O viršutinė riba (n * log (n)). Jis naudoja „kilpų iteracijas“, kurios padidina skaičių dalimis, o ne 1. Pavyzdžiui. Kai n yra 6, iteracijų skaičius yra 6 + 3 + 2 + 1,5 + 1,2 + 1 = 14,7, o ne 6 + 3 + 2 + 2 + 2 + 1 = 16. Šis skirtumas yra santykinai mažesnis. kaip n padidėja, taigi šiek tiek mažiau nei O (n * log (n)) augimas. Todėl, ignoruojant kodą, naudojamas sveikasis skaičius matematika, turime daug sudėtingesnį klausimą.


2019