Klausimai, pažymėti „big-o“

Žymėjimas Big-O naudojamas asimptotinėms viršutinėms riboms žymėti. Jame aprašomas atitinkamas algoritmų laiko ar erdvės sudėtingumas. „Big-O“ analizė suteikia grubų ir supaprastintą problemų problemų įvertinimą.
39
atsakymai

Kas yra paprastas „Big O“ anglų kalbos paaiškinimas?

Norėčiau, kad būtų kuo mažiau formalios apibrėžties ir paprastos matematikos.
nustatyti 28 sausis '09 14:10
31
atsakymas

Ką reiškia O (log n)?

Šiuo metu studijuoju „Big O Notation“ vykdymo laiką ir nusidėvėjimo laiką. Suprantu tiesinio laiko O (n) sąvoką, o tai reiškia, kad įėjimo dydis proporcingai įtakoja algoritmo augimą ... ir tas pats taikoma, pavyzdžiui, kvadratiniam laikui.
nustatyti 21 vas '10, 23:05
23
atsakymai

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 jūs vis dar galite ...
nustatyti rugpjūčio 06 d '08, 13:18
5
atsakymai

Nuolatinis amortizuotas laikas

Ką reiškia „Nuolatinis amortizuotas laikas“, kai kalbama apie algoritmo sudėtingumą?
14 val. '08 11:32
9
atsakymai

Koks skirtumas tarp Θ (n) ir O (n)?

Kartais matau n (n) keistą simbolį Θ su kažkuo tarp ir kartais tik O (n). Ar tai tiesiog pernelyg tingus, nes niekas nežino, kaip rašyti šį simbolį, ar tai reiškia kažką kito?
nustatytas sausio 23 d '09 - 1:58
34
atsakymai

Ar yra kokių nors O (1 / n) algoritmų?

Ar yra kokių nors O (1 / n) algoritmų? Arba kas nors mažesnė nei O (1)?
gegužės 25 d., 09:15
25
atsakymai

Big-O aštuonerių metų amžiaus?

Klausiu daugiau apie tai, ką tai reiškia mano kodui. Suprantu matematines sąvokas, man tiesiog nesunku suvynioti galvą apie tai, ką jie reiškia konceptualiai. Pavyzdžiui, jei kas nors turi atlikti O (1) operaciją duomenų struktūroje, aš ...
nustatytas rugsėjo 20 d '08, 7:59
12
atsakymai

Fibonacci sekos skaičiavimo sudėtingumas

Suprantu „Big-O“ įrašą, bet nežinau, kaip ją apskaičiuoti daugeliui funkcijų. Visų pirma, aš bandžiau išsiaiškinti Naivos Fibonacci sekos skaičiavimo sudėtingumą: int Fibonacci (int n) {jei (n <= 1) grįžta n; dar ...
gruodžio 11 d '08 11:20 val
4
atsakymai

„Big-O“ funkcijų sąrašas PHP

Kai kurį laiką naudojote PHP, pastebėjau, kad ne visos PHP yra įdėtos į funkcijas taip greitai, kaip tikėtasi. Apsvarstykite žemiau dvi galimas funkcijas, kurios randamos, jei skaičius yra paprastas, naudojant talpyklą, kurioje yra paprastas paprastas ...
nustatykite kovo 19 d. 10 val
22
atsakymai

Ar yra atvejų, kai pageidaujate didesnio sudėtingo sudėtingumo algoritmo, palyginti su mažesniu?

Ar yra atvejų, kai pageidaujate O (log n) laiko sudėtingumo O (1) laiko sudėtingumui? Arba O (n) į O (log n)? Ar turite kokių nors pavyzdžių?
nustatyti 09 gruodis '15, 16:25
3
atsakymai

Skirtumas tarp Big-O ir Little-O pastabų

Koks yra skirtumas tarp Big-O O (n) ir Small-O O (n) žymėjimo?
nustatytas 01 rugsėjis '09 23:22
14
atsakymai

Įtraukti elementą į sąrašą R, nuvertėjusio laiko konstanta, O (1)?

Jei turiu Rylistą, galite jį pridėti kaip elementą: mylist [[ilgis (mylist) +1]] <- obj Bet, žinoma, yra dar kompaktiškesnis būdas. Kai buvau naujas R, bandžiau rašyti lappend () tokį: lappend <-...
kovo 13 d. 10 val
32
atsakymai

Kaip rasti kth didžiausią elementą nerūšiuotoje masyvo ilgyje n ilgio O (n)?

Manau, kad yra būdas rasti kth didžiausią elementą nerūšiuotoje masyvo ilgyje n (O). O gal tai buvo „tikimasi“ O (n) ar kažkas kito. Kaip tai padaryti?
Nustatyti spalio 31 d '08 0:06
10
atsakymai

Ar log (n!) = Θ (n · log (n))?

Turiu parodyti, kad log (n!) = Θ (n · log (n)). Pateikta nuoroda, kad turėčiau parodyti viršutinę ribą nn ir parodyti apatinę ribą (n / 2) (n / 2). Man atrodo neįdomu. Kodėl taip yra? Aš tikrai galiu pamatyti, kaip konvertuoti ...
nustatyti 19 sausis '10, 20:15
5
atsakymai

Ar 2 ^ n ir n * 2 ^ n tuo pačiu metu yra sudėtingi?

Ištekliai, kuriuos atradau laiko sudėtingumu, nėra aiškūs, kai terminų sudėtingumo laiko lygtis gali būti ignoruojami, ypač su ne polinominiais pavyzdžiais. Man aišku, kad, atsižvelgiant į kažką panašaus į n 2 + n + 1, paskutiniai du nariai nėra ...
nustatytas vasario 13 d '14, 23:32