Klausimai su žyma „sudėtingumo teorija“

Skaitmeninio sudėtingumo teorija yra teorinės kompiuterinės mokslo ir matematikos skaičiavimo teorijos dalis, kurioje pagrindinis dėmesys skiriamas skaičiavimo problemų klasifikavimui pagal jų sudėtingumą. Ypač dažni programavimo metu yra * laiko ir erdvės amortizuota analizė *
3
atsakymai

Rekursinių funkcijų sudėtingumo nustatymas („Big O“ įrašas)

Rytoj turiu kompiuterių mokslų ir man reikia pagalbos nustatant šių rekursinių funkcijų sudėtingumą. Žinau, kaip išspręsti paprastus atvejus, bet vis dar bandau išmokti išspręsti šias sudėtingesnes bylas. Tai buvo tik keletas problemų pavyzdžių ...
nustatyti lapkričio 20 d '12 9:28
6
atsakymai

HashMap gauna / įdėkite sudėtingumą

Mes esame įpratę sakyti, kad HashMap gauti / įdėti operacijos yra O (1). Tačiau tai priklauso nuo maišos įgyvendinimo. Numatytasis maišos iš tikrųjų yra vidinis JVM krūvos adresas. Esame įsitikinę, kad pakanka pasakyti, kad gauti / įdėti yra O (1)? D ...
gruodžio 29 d '11, 14:22
11
atsakymai

Kas yra greičiausias algoritmas susieti susietą sąrašą?

Aš smalsu, jei O (n log n) gali geriausiai susieti sąrašą.
nustatyti spalio 06 '09 14:51 val
2
atsakymai

Kas gali sukelti O (log log n) algoritmo sudėtingumą?

Šis ankstesnis klausimas apibūdina kai kuriuos veiksnius, kurie gali sukelti O (log n) algoritmo sudėtingumą. Kas gali lemti tai, kad algoritmas turi laiko sudėtingumą O (log log n)?
gegužės 10 d. 13 val
8
atsakymai

Didelis prieš didelį teta

Galimas dublikatas: koks yra skirtumas tarp Θ (n) ir O (n)? Man atrodo, kad kai žmonės neoficialiai kalba apie algoritmo sudėtingumą, jie kalba apie didįjį. Tačiau formaliose situacijose aš dažnai matau didelį teta su retkarčiais dideliu omu. Aš esu matematika ...
Nustatyta liepos 12 d
7
atsakymai

O (N log N) Sunkumas - kaip linijinis?

Todėl manau, kad jie palaidos mane užduoti tokį trivialų klausimą, bet aš šiek tiek painu. Aš įgyvendinau „quicksort“ programinę įrangą „Java“ ir „C“, ir aš atlikiau keletą pagrindinių palyginimų. Grafikas išėjo kaip dvi tiesios linijos, o C buvo 4 ms greičiau nei Java-a ...
birželio 07 d
7
atsakymai

Paaiškinkite Vinay Deolilikar įrodymą, kad P! = NP

Neseniai buvo paskelbtas „Vinay Deolilicar“ paskelbtas straipsnis „HP Labs“, kuriame teigiama, kad įrodė, jog P! = NP. Ar kas nors gali paaiškinti, kaip šis įrodymas veikia mažiau matematiškai linkusiems žmonėms?
nustatyti 09 rug. '10, 5:22
8
atsakymai

Bendrosios SQL pranešimų supaprastinimo taisyklės

Aš ieškau kai kurių „išvesties taisyklių“ (panašių į apibrėžtas veiklos taisykles ar logines taisykles), kurias galiu naudoti, kad sumažintumėte SQL užklausą pagal sudėtingumą ar dydį. Ar yra kažkas panašaus? Bet kokie dokumentai, įrankiai? Kas yra ekvivalentas ...
yra nustatytas liepos 01'09, 17:14
7
atsakymai

Kaip suprasti problemą su kuprinė „NP-complete“?

Mes žinome, kad nugaros problema gali būti išspręsta O (nW) sudėtingumu dinamišku programavimu. Tačiau mes sakome, kad tai yra visa NP problema. Manau, kad čia sunku suprasti. (n yra elementų skaičius. W yra didžiausias tūris.)
nustatyti spalio 11 d. '10, 18:17
3
atsakymai

Kas yra O (log * N)?

Kas yra O (log * N)? Aš žinau, didelis - Oh, log * nežinomas.
nustatytas kovo 05d
3
atsakymai

daugialypės terpės, žemėlapių ir sunkumų žemėlapių

Norėčiau sužinoti, kiek sudėtinga yra multiset klasių, žemėlapių ir STL maišos kortelių „Big O“ žymėjimas: Įrašų įrašymas, prieiga prie įrašų, įrašų išrašymas, įrašų palyginimas.
nustatyti spalio 21 d '08 8:02 val
1
atsakymas

Kodėl SortedSet <T> .GetViewBetween ne O (log N)?

„NET 4.0+“ kategorijoje „SortedSet <T>“ yra metodas, vadinamas GetViewBetween (l, r), kuris grąžina sąsajos vaizdą medžio dalyje, kurioje yra visos vertės tarp šių dviejų. Atsižvelgiant į tai, kad „SortedSet <T>“ yra įdiegta kaip raudona ir juoda ...
Nustatykite kovo 24 d. 12 val
6
atsakymai

Ar Big log (logn) bazinė duomenų bazė?

Duomenų struktūros paieškos dvejetainio medžio tipui matau, kad Big O įrašas paprastai žymimas kaip O (logn). Mažosios raidės „l“ žurnale tai reiškia duomenų bazę e (n), kaip aprašyta natūraliame logaritmu? Atsiprašome už paprastą klausimą, bet aš esu ...
15 val. '09 3:28
7
atsakymai

Ar žinomo statistinio paskirstymo duomenų rūšiavimo algoritmai?

Man tiesiog atsitiko, kad jei žinote kažką apie rūšiuojamų duomenų platinimą (statistiniu požiūriu), rūšiavimo algoritmo veikimas gali būti naudingas, jei atsižvelgiate į šią informaciją. Taigi mano klausimas yra, ar aš ...
gegužės 29 d. 11 val
4
atsakymai

B-Tree vs Hash lentelė

MySQL indekso tipas yra b-medis, o prieiga prie elemento b-medyje atliekama logaritminiu aritmetiniu laiku O (log (n)). Kita vertus, prieiga prie elemento maišos lentelėje yra O (1). Kodėl maišymo lentelė nenaudojama vietoj b ...
nustatyti 05 Rgs '11 12:43