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ė *
7
atsakymai

Ar sąrašas :: dydis () tikrai O (n)?

Neseniai pastebėjau, kad kai kurie žmonės pastebėjo, kad std :: list :: size () yra linijinis. Pasak kai kurių šaltinių, tai iš tikrųjų priklauso nuo įgyvendinimo, nes standartas nesako, koks sudėtingumas turėtų būti. Šio įrašo komentaras yra ...
nustatyti spalio 23 d '08 11:08
6
atsakymai

Ar O (n) algoritmas gali viršyti O (n ^ 2) skaičiavimo laiko atžvilgiu?

Tarkime, aš turiu du algoritmus: už (int i = 0; i <n; i ++) {už (int j = 0; j <n; j ++) {// kažką pastoviu laiku}} Tai natūralus O (n ^ 2). Tarkime, aš taip pat turiu: už (int i = 0; i <100; i ++) {...
yra nustatytas kovo 23 d., 14 val
7
atsakymai

Kodėl šio algoritmo O (n ^ 2) Big-O sudėtingumas?

Žinau, kad šio algoritmo sudėtingumas yra O (n ^ 2), bet negaliu suprasti, kodėl. int sum = 0; int i = 1; j = n * n; o (i ++ <j--) sum ++; Net jei pradžioje nustatėme j = n * n, mes padidiname i ir sumažiname j kiekvienu iteracijos metu
lapkričio 22 d. '15, 10:02 val
9
atsakymai

Galima naudoti C + +?

Paprastai naudoju C + + stdlib kortelę, kai reikia saugoti kai kuriuos duomenis, susijusius su tam tikros rūšies verte (pagrindinė vertė - pavyzdžiui, eilutė ar kitas objektas). Stdlib kortelės įdiegimas grindžiamas medžiais, kurie suteikia geriausius pr ...
nustatyti 25 rugsėjis '08 17:11
5
atsakymai

laiko sudėtingumas ir perjungimas (), palyginti su „push“ () „JavaScript“

Žinau skirtumą tarp „nestandartinių“ () ir „push“ () metodų „Javascript“, bet man įdomu, koks yra laiko sudėtingumo skirtumas? Manau, kad push () metodas yra O (1), nes jūs tiesiog įtraukiate elementą į masyvo pabaigą, bet nesu tikras dėl u metodo ...
nustatytas 03 rugsėjis '12 18:33
4
atsakymai

Kokia yra įprastos išraiškos sudėtingumas?

Kokie sunkumai kyla dėl eilutės ilgio, kurį reikia lyginti eilutėje esančias eilutes?
nustatyti 07 gruodis '10, 18:38
3
atsakymai

Kodėl problema kyla dėl kuprinės pseudo polinomo?

Žinau, kad „Knapsack“ yra „NP“, tačiau ją gali įgalinti DP. Manoma, kad DP tirpalas yra pseudo-polinomas, nes jis yra eksponentinis „įvesties ilgyje“ (t. Y. Bitų, reikalingų įvesties kodavimui). Deja, man tai nepatinka ...
gruodžio 27 d '11 15:19
6
atsakymai

.NET konsolės programos įvykių išėjimas

Ar .NET turi metodą, pvz., Įvykį, konsolės išėjimui aptikti? Turiu išvalyti kai kurias temas ir COM objektus. Iš konsolės programos paleidžiu pranešimų ciklą be formos. DCOM komponentas, kurį naudoju, atrodo ...
liepos 13 d., 17:38
13
atsakymai

Kas yra su O (1)?

Pastebėjau labai keistą O (1) naudojimą diskusijose apie algoritmus, susijusius su maišymo ir paieškos tipais, dažnai vartojant kalbos sistemos pateiktą žodyno tipą arba naudojant žodyno ar hash masyvo tipus, naudojant ...
nustatyti 02 gruodis '08 6:29
30
atsakymai

Ar žaidimai yra sudėtingiausi / įspūdingiausi?

Šiandien mąstau apie tai, kas gali būti sudėtingiausia / įspūdingiausia paraiška. Todėl pradėjau galvoti apie tai, ką jaučiuosi patogiai ir naudoju kasdienines duomenų bazes. Tada aš įžengiau į nežinomą lauką (daugumai iš mūsų, ...
14 vasario mėn. '09 5:18
5
atsakymai

Koks yra „python“ sąrašo funkcijų vykdymo sudėtingumas?

Aš parašiau python funkciją, kuri atrodė taip: def foo (some_list): i intervale (0, len (some_list)): baras (some_list [i], i), kad jis būtų vadinamas naudojant x = [0, 1, 2, 3, ...] foo (x) Maniau, kad prieiga prie indekso yra sąrašas ...
nustatyti birželio 17 d., 09:28
6
atsakymai

Kas yra O reikšmė (polilog (n))? Visų pirma, kaip apibrėžiamas polylogue (n)?

Trumpai tariant, kai akademiniai (kompiuteriniai) straipsniai sako „O (polylog (n))“, ką jie reiškia? Nejaučiu „Big-Oh“ pastabos, kurią aš labai gerai pažįstu, bet veikiau su polylog (n) funkcija. Jie nekalba apie sudėtingą analizės funkciją Li ...
lapkričio 26 d. '09 4:45
8
atsakymai

Kodėl prieigos prie masyvo elemento laikas yra pastovus?

Tarkime, kad turiu masyvą: int a [] = {4,5,7,10,2,3,6}, kai kalbu apie elementą, pavyzdžiui, [3], kas iš tikrųjų vyksta užkulisiuose? Kodėl tiek daug algoritmų knygų (pvz., Cormen knyga ...) sako, kad ji užima pastovią
nustatyti 04 rugsėjis '11 10:31
7
atsakymai

Laiko sudėtingumo ir erdvės sudėtingumo skirtumai?

Mačiau, kad daugeliu atvejų laiko sudėtingumas yra susijęs su erdviniu sudėtingumu ir atvirkščiai. Pvz., Peržengiant masyvą: i = 1 iki ilgio (v) spausdinimo (v [i]) pabaigoje aukščiau minėtu atveju, lengva matyti, kad algoritmo sudėtingumas laiku ...
nustatyti 08 rugsėjis '13, 19:41
12
atsakymai

Kokie yra „Drupal“ trūkumai?

„Drupal“ yra „Do-It-All CMS“. Yra moduliai, kurie leidžia pridėti beveik bet kokią funkciją, kuri yra puiki. Tačiau atrodo, kad daugelis funkcijų (v5 ir v6) yra išsibarsčiusios naudotojui. Kaip sukurti ...
15 Jan '09 21:27