Didelis O, kaip tai apskaičiuoti?

Dauguma žmonių, turinčių laipsnį CS, tikrai žino, ką reiškia „Big O“ . Tai padeda mums išmatuoti algoritmo efektyvumą ir, jei žinote, kokioje kategorijoje yra problema, kurią bandote išspręsti, galite sužinoti, ar ji vis dar gali išspausti šį nedidelį papildomą našumą. 1

Bet aš smalsu, kaip apskaičiuojate ar apytiksliai algoritmų sudėtingumą?

1 , bet, kaip sakoma, neperpildykite, per anksti optimizavimas yra visų blogių šaknis , o optimizavimas be pagrįstos priežasties taip pat nusipelno šio pavadinimo.

722
06 авг. nustatyti sven 06 rug. 2008-08-06 13:18 '08 13:18 pm 2008-08-06 13:18
@ 23 atsakymai

Aš esu vietinio universiteto dėstytojas asistentų duomenų struktūros ir algoritmų kursams. Aš darysiu viską, ką galėčiau paaiškinti čia paprastais žodžiais, bet būkite atsargūs, kad ši tema priverstų mano mokinius suprasti keletą mėnesių. Daugiau informacijos rasite 2 skyriuje „ Duomenų struktūros ir algoritmai Java“ .


Nėra jokių mechaninių procedūrų, kuriomis būtų galima gauti „BigOh“.

Kaip „kucharską“, kad gautumėte šios funkcijos skaičiavimo sudėtingumą

 Number_Of_Steps = f(N) 

Taigi, mes turime f(N) , skaičiavimo etapų skaičiavimo funkciją. Funkcijos įrašas yra apdorojamos struktūros dydis. Tai reiškia, kad ši funkcija vadinama:

 Number_Of_Steps = f(data.length) 

Parametras N įgauna duomenų duomenų data.length . Dabar mums reikia tikrosios f() . Tai daroma iš šaltinio kodo, kuriame kiekviena įdomi eilutė yra sunumeruota nuo 1 iki 4.

Yra daug būdų apskaičiuoti „BigOh“. Nuo šiol darysime prielaidą, kad kiekvienas sakinys, kuris nepriklauso nuo įvesties duomenų dydžio, atlieka pastovius skaitinius žingsnius C

Į funkciją ketiname pridėti atskirą skaičių veiksmų, ir nei vietinio kintamojo, nei grįžimo operatoriaus deklaracija nepriklauso nuo data masyvo dydžio.

Tai reiškia, kad 1 ir 4 eilutės paima C pakopų skaičių, o funkcija yra maždaug tokia:

 f(N) = C + ??? + C 

Kita dalis - nustatyti ataskaitos vertę. Atminkite, kad skaičiuojame skaičiavimo etapų skaičių, o tai reiškia, kad operatoriaus korpusas įvykdomas N kartus. Tas pats, kaip pridedant C , N kartus:

 f(N) = C + (C + C + ... + C) + C = C + N * C + C 

Nėra jokių mechaninių taisyklių, kad būtų galima apskaičiuoti, kiek kartų kūnas yra įvykdytas, ir reikia jį suskaičiuoti, žiūrėdami į kodą. Siekiant supaprastinti skaičiavimus, ignoruojame kintamojo iniciaciją, būseną ir papildomas operatoriaus dalis.

Norint gauti faktinį BigOh, mums reikia asimptotinės funkcijos analizės . Tai apytiksliai padaryta taip:

  • Pašalinti visas C konstantas C
  • f() gaukite poliomiją standard form .
  • Atskirkite polinomo narius ir juos suskirstykite pagal augimo tempą.
  • Laikykitės didėjančio, kai N artėja prie infinity .

Mūsų f() turi du narius:

 f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1 

Mes pašaliname visas C konstantas ir nereikalingas dalis:

 f(N) = 1 + N ^ 1 

Kadangi paskutinis terminas yra didesnis, kai f() artėja prie begalybės (pagalvokite apie apribojimus ), šis argumentas yra BigOh, o funkcijų sum() turi reikšmę BigOh:

 O(N) 

Yra keletas triukų, kaip išspręsti kai kurias sudėtingas užduotis: naudokite sumas, kai tik galite.

Pavyzdžiui, šį kodą galima lengvai išspręsti naudojant sumavimą:

 for (i = 0; i < 2*n; i += 2) { // 1 for (j=n; j > i; j--) { // 2 foo(); // 3 } } 

Pirmas dalykas, kurį turėjote užduoti, buvo foo() vykdymo tvarka. Nors normalus turėtų būti O(1) , turite paklausti savo profesorių apie tai. O(1) reiškia (beveik iš esmės) pastovumą C , nepriklausomai nuo N dydžio.

Pirmasis sakinio sakinys yra sudėtingas. Kol indeksas baigiasi 2 * N , prieaugį atlieka du. Tai reiškia, kad pirmasis gauna tik N žingsnius ir turime suskirstyti rezultatą į du.

 f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = = Summation(i from 1 to N)( ... ) 

Antrasis sakinys yra dar sudėtingesnis, nes jis priklauso nuo i vertės. Pažvelkite: rodyklė, į kurią atsižvelgsiu, yra: 0, 2, 4, 6, 8, ..., 2 * N, o antrasis - įvykdomas: N pirmą kartą, N - 2 sekundė, N - 4 trečia ... prieš N / 2, kur antroji niekada nebus vykdoma.

Pagal formulę tai reiškia:

 f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) ) 

Dar kartą skaičiuokite žingsnių skaičių . Ir pagal apibrėžimą, kiekviena suvestinė visada turi būti pradedama nuo vieno ir baigiama skaičiumi, kuris yra didesnis arba lygus vienam.

 f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) ) 

(Manome, kad foo() yra O(1) ir imasi veiksmų C )

Turime problemą: kai i paimsiu vertę N / 2 + 1 , vidinis sumavimas baigiasi neigiamu skaičiumi! Tai neįmanoma ir neteisinga. Mums reikia suskirstyti pusę, tai yra posūkio taškas, momentas, kai i užtrunka N / 2 + 1 .

 f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C ) 

Kadangi pagrindinis taškas yra i > N / 2 , vidinis for tai nebus vykdomas, ir mes prisiimame nuolatinį C atlikimo savo kūno sudėtingumą.

Dabar sumos gali būti supaprastintos naudojant kai kurias identifikavimo taisykles:

  • Sumavimas (w nuo 1 iki N) (C) = N * C
  • Sumavimas (w nuo 1 iki N) (A (+/-) B) = sumavimas (w nuo 1 iki N) (A) (+/-) Summacija (w nuo 1 iki N) (B)
  • Sumažinimas (w nuo 1 iki N) (w * C) = C * suvienodinimas (w nuo 1 iki N) (w) (C yra konstanta, nepriklausoma nuo w )
  • Sumavimas (w nuo 1 iki N) (w) = (N * (N + 1)) / 2

Kai kurių algebrų taikymas:

 f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C ) f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C ) f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C ) => Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i ) f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C ) => (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = (N / 2 - 1) * (N / 2) / 2 = ((N ^ 2 / 4) - (N / 2)) / 2 = (N ^ 2 / 8) - (N / 4) f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C ) f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2) f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2) f(N) = C * ( N ^ 2 / 4 ) + C * N f(N) = C * 1/4 * N ^ 2 + C * N 

Ir BigOh:

 O(N²) 
 O(N²) 
1340 m
31 янв. atsakymas pateikiamas vz0 sausio 31 d 2011-01-31 18:33 '11, 18:33, 2011-01-31 18:33

Didelis O suteikia viršutinę ribą algoritmo laiko sudėtingumui. Paprastai jis naudojamas kartu su duomenų rinkinių (sąrašų) apdorojimu, bet gali būti naudojamas kitur.

Keletas pavyzdžių, kaip jis naudojamas C kode.

Tarkime, mes turime n elementų masyvą

 int array[n]; 

Jei norėtume pasiekti pirmąjį masyvo elementą, tai būtų O (1), nes nesvarbu, kiek masyvas yra, tas pats pastovus laikas visada reikalingas norint gauti pirmąjį elementą.

 x = array[0]; 

Jei sąraše norėjome rasti numerį:

 for(int i = 0; i < n; i++){ if(array[i] == numToFind){ return i; } } 

Tai bus O (n), nes geriausiu atveju turėsime ieškoti viso sąrašo ir surasti mūsų numerį. Big-O vis dar yra O (n), nors mes galime rasti savo skaičių pirmuoju bandymu ir praleisti ciklą vieną kartą, nes Big-O apibūdina viršutinę algoritmo ribą (omega apatinei ribai ir teta glaudžiam susiejimui).

Kai gauname įdėtos kilpos:

 for(int i = 0; i < n; i++){ for(int j = i; j < n; j++){ array[j] += 2; } } 

Tai yra O (n ^ 2), nes kiekvienam išorinės kilpos (O (n)) praėjimui dar kartą turime pereiti per visą sąrašą, kad galėtume dauginti n mums su kvadratu n.

Ji vos įbrėžia paviršių, bet kai pereinate prie sudėtingesnių algoritmų analizės, pradedama taikyti sudėtinga matematika su įrodymais. Tikiuosi, kad tai jus supažindins su pagrindais, bent jau.

184
06 авг. DShook atsakymas 2008-08-06 16:34 '08 at 4:34 pm 2008-08-06 16:34

Nors žinant, kaip nustatyti konkrečios problemos „Big O“ laiką, yra naudinga, žinant, kad kai kurie dažni atvejai gali labai padėti priimti sprendimus savo algoritme.

Štai keletas dažniausių atvejų, paimtų iš http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1) - nustatyti, ar numeris yra lygus, ar nelyginis; naudojant fiksuoto dydžio paieškos lentelę arba maišos lentelę

O (logn) - ieškoti elemento rūšiuojamajame masyve su dvejetainiu ieškojimu.

O (n) - ieškoti elemento nerūšiuotame sąraše; pridėti du n-skaitmenų numerius

O (n 2 ) - dviejų n-skaitmenų skaičių dauginimas paprastu algoritmu; pridedant dvi n × n matricas; burbuliukų rūšiavimas arba rūšiavimas

O (n 3 ) - dviejų n × n matricų dauginimas su paprastu algoritmu

O (c n ) - Kelionės pardavėjo problemos (tikslaus) sprendimo paieška naudojant dinaminį programavimą; nustatyti, ar du loginiai operatoriai yra lygiaverčiai naudojant brutalią jėgą

O (n!) - Kelionės pardavėjo problemos sprendimas, ieškant brutalios jėgos

O (n n ) - dažnai naudojamas vietoj O (n!) Norėdami gauti paprastesnes formules asimptotiniam sudėtingumui

83
05 сент. Giovanni Galbo atsakymas 05 Sep. 2008-09-05 22:09 '08 22:09 val. 2008-09-05 22:09

Nedidelis priminimas: big O simbolis naudojamas asimptotiniam sudėtingumui nurodyti (ty kai problemos dydis didėja iki begalybės), ir jis slepia konstantą.

Tai reiškia, kad tarp algoritmo O (n) ir vienas O (n 2 ) greičiausiai ne visada yra pirmasis (nors visada yra tokia reikšmė n, kad dydžio problemai> n, pirmasis algoritmas yra greičiausias).

Atkreipkite dėmesį, kad paslėpta konstanta labai priklauso nuo įgyvendinimo!

Be to, kai kuriais atvejais vykdymo aplinka nėra n dydžio įvesties deterministinė funkcija. Pavyzdžiui, rūšiavimas atliekamas naudojant greitą tvarką: laikas, reikalingas n elementų masyvo rūšiavimui, nėra pastovus, bet priklauso nuo pradinės masyvo konfigūracijos.

Yra įvairių laiko sunkumų:

  • Blogiausias atvejis (paprastai paprasčiausias būdas išsiaiškinti, nors ne visada labai reikšmingas)
  • Vidutinis dydis (paprastai sunkiau išsiaiškinti)

  • ...

Geras įvadas - R.Sedzhuiko ir P.Fleioleto algoritmų analizės įvadas.

Kaip jūs sakote, premature optimisation is the root of all evil ir, jei įmanoma, optimizuojant kodą, visada turėtų būti naudojamas profiliavimas. Tai gali netgi padėti nustatyti algoritmų sudėtingumą.

38
23 авг. atsakymas pateikiamas OysterD 23 rug . 2008-08-23 23:43 '08, 23:43 pm 2008-08-23 23:43

Matydami čia pateiktus atsakymus, manau, kad galime daryti išvadą, kad dauguma iš mūsų tikrai suderina algoritmo tvarką, žiūri į ją ir naudodamiesi sveiku protu, o ne skaičiuodami, pvz., Pagrindinį metodą , kaip manėme universitete. Be to, turiu pridurti, kad net ir profesorius paragino mus (vėliau) galvoti apie tai, o ne tik suskaičiuoti.

Taip pat norėčiau pridurti, kaip tai daroma rekursinėms funkcijoms :

Tarkime, kad turime tipo funkciją ( schemos kodą ):

 (define (fac n) (if (= n 0) 1 (* n (fac (- n 1))))) 

kuris rekursiškai apskaičiuoja tam tikro skaičiaus faktorių.

Pirmas žingsnis yra bandyti nustatyti funkcijų kūno veikimo charakteristikas tik šiuo atveju, nieko ypatingo nėra organizme, tiesiog dauginti (arba grąžinti vertę 1).

Taigi, kūno veikimas : O (1) (pastovus).

Tada pabandykite ir nustatykite rekursinių skambučių skaičių. Šiuo atveju turime n-1 rekursinius skambučius.

Taigi rekursinių skambučių našumas yra O (n-1) (tvarka n, nes mes išskiriame neesmines dalis).

Tada įdėkite šiuos du kartu ir tada gausite viso rekursijos funkcijos našumą:

1 * (n-1) = O (n)


Petras atsakys į iškeltus klausimus; Būdas, kurį čia apibūdinau, iš tikrųjų jį tvarko gana gerai. Tačiau atminkite, kad tai vis dar yra apytikslis, o ne pilnas matematinis teisingas atsakymas. Čia aprašytas metodas taip pat yra vienas iš universiteto mokymo metodų, ir, jei aš teisingai prisimenu, jis buvo naudojamas pažangesniems algoritmams nei šiame pavyzdyje naudojamas faktorius. Žinoma, viskas priklauso nuo to, kaip gerai galite įvertinti laiko funkciją ir rekursinių skambučių skaičių, tačiau tai pasakytina ir apie kitus metodus.

25
07 авг. atsakymą pateikė sven 07 rug. 2008-08-07 11:10 '08 at 11:10 am 2008-08-07 11:10

Jei jūsų vertė yra polinomas, tiesiog laikykite aukštesniojo užsakymo narį be jo daugiklio. Pavyzdžiui:

O ((n / 2 + 1) * (n / 2)) = O (n 2/4 + n / 2) = O (n 2/4) = O (n 2 )

Tai neveikia begalinėms eilėms, nepamirškite. Apskritai nėra vieno recepto, nors kai kuriais atvejais taikomi šie skirtumai:

O (log N) O (N) O (N log N) O (N2) <O (N k ) <O ( en ) <O (n!)

23
31 янв. Marcelo Cantos atsakymas, sausio 31 d 2011-01-31 16:30 '11, 16:30, 2011-01-31 16:30

Aš galvoju apie tai informacijos prasme. Bet kokia problema yra tirti tam tikrą bitų skaičių.

Jūsų pagrindinė priemonė yra sprendimų taškų ir jų entropijos samprata. Sprendimo taško entropija yra vidutinė informacija, kurią ji suteikia jums. Pavyzdžiui, jei programoje yra sprendimo taškas su dviem atšakais, tada entropija yra kiekvieno filialo tikimybės suma log 2 , kuris yra šios šakos tikimybės atvirkštinis dydis. Štai ką jūs išmoksite atlikdami šį sprendimą.

Pavyzdžiui, if , turintis dvi šakas, kurios yra vienodai tikėtinos, turi 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Taigi, jo entropija yra 1 bitas.

Tarkime, kad ieškote N elementų lentelės, pvz., N = 1024. Tai 10 bitų problema, nes žurnalas (1024) = 10 bitų. Todėl, jei galite ieškoti IF ataskaitų, turinčių vienodai tikėtinus rezultatus, jis turi priimti 10 sprendimų.

Ką gaunate su dvejetainiu paieška.

Tarkime, kad atliekate tiesinę paiešką. Pažvelkite į pirmąjį elementą ir paklauskite, ar norite to, kurį norite. Tikimybės yra 1/1024, o tai yra ir 1023/1024, o taip nėra. Šio tirpalo entropija yra 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * apie 0 = apie 0,01 bitų. Jūs labai mažai išmokote! Antrasis sprendimas nėra geresnis. Štai kodėl linijinės paieškos yra tokios lėtos. Tiesą sakant, tai yra eksponentinis bitų, kuriuos reikia išmokti, skaičiumi.

Tarkime, jūs darote indeksą. Tarkime, kad lentelė yra iš anksto surūšiuota į kelias dėžes, ir naudodami kai kuriuos raktus esančius bitus indeksuokite tiesiogiai į lentelės įrašus. Jei yra 1024 bunkeriai, visų 1024 galimų rezultatų atveju entropija yra 1/1024 * log (1024) + 1/1024 * log (1024) + .... Tai yra 1/1024 * 10 kartų 1024 rezultatai arba 10 bitų entropijos šiai indeksavimo operacijai. Todėl indeksų paieška yra greita.

Dabar pagalvokite apie rūšiavimą. Turite N elementų ir turite sąrašą. Kiekvienam elementui reikia rasti, kur elementas yra sąraše, tada pridėkite jį prie sąrašo. Taigi rūšiavimas trunka apie N kartų daugiau nei pagrindinės paieškos etapų.

Taigi rūšiavimas, pagrįstas dvejetainiais sprendimais, turinčiais apytikriai vienodai tikėtinus rezultatus, yra laikomas O (N log N) pakopomis. O (N) rūšiavimo algoritmas galimas, jei jis yra pagrįstas indekso paieška.

Radau, kad beveik visas su algoritminiu veikimu susijusias problemas galima peržiūrėti tokiu būdu.

18
10 марта '09 в 16:24 2009-03-10 16:24 atsakė Mike Dunlavey kovo 10 d., 09:24, 2009-03-10 16:24

Pradėkime nuo pat pradžių.

Visų pirma, sutinku su principu, kad kai kurias paprastas duomenų operacijas galima atlikti O(1) laiku, ty laiku, kuris nepriklauso nuo įvesties dydžio. Šios primityvios operacijos C sudaro

  • Aritmetinės operacijos (pvz., + Arba%).
  • Palyginimo operacijos (pvz., <=).
  • Prieigos prie struktūros operacijų (pvz., Masyvo indeksavimas, pvz., A [i] arba žymeklis, naudojant → operatorių).
  • Paprasta užduotis, pvz., Vertės kopijavimas į kintamąjį.
  • Skambinimas bibliotekos funkcijoms (pvz., Scanf, printf).

Šio principo pagrindimas reikalauja išsamaus kompiuterio instrukcijų (primityvių žingsnių) išsamaus tyrimo. Kiekvieną iš aprašytų operacijų galima atlikti su nedideliu skaičiumi mašinų komandų; dažnai reikalingi tik vienas ar du nurodymai. Todėl keletas C išraiškų gali būti įvykdytos O(1) laiku, ty tam tikru pastoviu laiku, nepriklausomai nuo įvesties. Šie paprasti yra

  • Priskyrimo operatoriai, neįtraukiantys funkcijų skambučių į savo išraiškas.
  • Skaitymo pareiškimai.
  • Parašykite argumentus, kurie nereikalauja funkcijų kvietimo.
  • Pereinamojo laikotarpio operatoriai pertraukia, tęsia, goto ir grąžina išraišką, kurioje išraiška neturi funkcijų.

C, daug for-loops yra suformuota inicijuojant indekso kintamąjį į tam tikrą vertę ir didinant šį kintamąjį 1 kartų kiekvieną aplink kilpą. Kontūro kontūras baigiasi, kai indeksas pasiekia tam tikrą ribą. Pavyzdžiui, for-loop

 for (i = 0; i < n-1; i++) { small = i; for (j = i+1; j < n; j++) if (A[j] < A[small]) small = j; temp = A[small]; A[small] = A[i]; A[i] = temp; } 

naudoja indekso kintamąjį i. Jis kiekvieną kartą didina mane po 1 kilpą, o iteracijos sustoja, kai pasiekiu n-1.

Tačiau, dabar, sutelkkite dėmesį į paprastą for-loop formą, kur skirtumas tarp galutinių ir pradinių verčių, padalytų iš indekso kintamo padidėjimo, rodo, kiek kartų mes einame aplink kilpą . Šis rezultatas yra tikslus, jei nėra jokių kilpos išėjimo takų naudojant šuolio nurodymus; tai yra viršutinė iteracijų skaičiaus riba.

Pavyzdžiui, for-loop iterates ((n − 1) − 0)/1 = n − 1 times , nes 0 yra pradinė vertė i, n - 1 yra didžiausia vertė, kurią pasiekiu (t.y., kai pasiekiu n -1, kilpa sustoja ir nėra iteracijos su i = n-1), ir 1 pridedamas prie i kiekvienoje kilpos iteracijoje.

Pats paprasčiausias atvejis, kai ciklo korpuse praleistas laikas kiekvienam iteracijai yra tas pats, mes galime padauginti didelę viršutinę kūno ribą per laiką aplink ciklą . Griežtai kalbant, mes turime pridėti O (1) laiką, kad pradėtume kilpos indeksą ir O (1) laiką, kad pirmiausia palygintumėte linijos indeksą su riba , nes mes bandome dar kartą, kaip mes einame aplink kilpą. Tačiau, jei galite atlikti nulinį ciklo laiką, laikas, per kurį reikia inicijuoti ciklą ir išbandyti ribą, yra jauniausias narys, kuris gali būti sumažintas sumavimo taisyklėje.


Dabar apsvarstykite šį pavyzdį:

 (1) for (j = 0; j < n; j++) (2) A[i][j] = 0; 

Mes žinome, kad eilutė (1) užima laiko O(1) . Ясно, что мы идем вокруг цикла n раз, так как мы можем определить, вычитая нижний предел из верхнего предела, найденного на линии (1), а затем добавление 1. Так как тело, строка (2), принимает время O (1), можно пренебречь время для увеличения j и время для сравнения j с n, оба из которых также O (1). Таким образом, время выполнения строк (1) и (2) является <сильным > произведением n и O (1), которое O(n) .