Big-O — nosauc koda sarežģītību
Izlasi fragmentu, nosauc tā laika sarežģītību, tad paskaties augšanas līkni. Sešas klases, seši raundi. Bez maksas.
Pieci fragmenti, piecas no sešām sarežģītības klasēm, katra jautāta vienu reizi.
Kā spēlēt
- Izlasi fragmentu un izvēlies tā laika sarežģītību no sešām.
- Augšanas līkne tiek uzzīmēta pēc katras atbildes: tava sarkanā, pareizā zaļā.
- Piecas klases no sešām braucienā, bez atkārtojumiem, tāpēc viena un tā pati atbilde ir pareiza augstākais vienreiz.
- Pareizas atbildes pēc kārtas dod vairāk. Nepareiza atiestata sēriju.
Kā tas darbojas
Katrs raunds parāda īsu koda gabalu un jautā tā laika sarežģītību. Tu atbildi, un tiek uzzīmēta augšanas līkne — tava pret pareizo — tā ka izvēle beidz būt tikai uzlīme un kļūst par formu, ko var redzēt. Viens brauciens jautā piecas klases no sešām, sajauktā secībā un bez atkārtojumiem, tātad atbildēt vienmēr vienu un to pašu ir pareizi augstākais vienu reizi — un izlaistā klase mainās, tāpēc pēdējais raunds nekad nav dāvana pēc izslēgšanas. Fragmenti izvēlēti tā, lai katram būtu viena aizstāvama atbilde: bez priekšlaicīgas izejas, bez slēptām bibliotēkas izmaksām un bez nekā, kas nodod savu sarežģītību komentārā. Kārtošana visur tiek uzskatīta par O(n log n) — tieši to piedāvā jebkura standarta bibliotēka. Viss darbojas tavā ierīcē, nekas nekur netiek sūtīts, un reģistrēties nav kur.
O apzīmējums apraksta, kā izmaksas aug, nevis cik tās ir. O(n²) ar labām konstantēm pārspēj uzpūstu O(n log n) tajos izmēros, ko redz lielākā daļa īstā koda — par to ir cita spēle šajā vietnē.
Biežāk uzdotie jautājumi
Kāpēc līkne ir logaritmiskā mērogā?
Tāpēc ka citādi sešas klases neietilpst vienā grafikā. Pie n=24 konstanta laika funkcija maksā 1, bet eksponenciāla — sešpadsmit miljonus, tāpēc uz lineāras ass piecas no sešām līknēm būtu viena un tā pati plakanā līnija pie apakšas. Logaritmiskais mērogs pārvērš katru klasi atšķiramā slīpumā, un tieši to ir vērts redzēt.
Vai kārtošana tiešām ir O(n log n)?
Salīdzināšanas kārtošanām jā — tā ir pierādīta apakšējā robeža un tas, ko piedāvā jebkura standarta bibliotēka. Skaitīšanas un ciparu kārtošana ir ātrākas, jo nesalīdzina, bet tām vajag pieņēmumus par atslēgām. Kad fragments šeit izsauc sort(), tas maksā n log n.
Kāpēc nav fragmentu ar priekšlaicīgu izeju?
Tāpēc ka priekšlaicīga izeja pārvērš sliktāko gadījumu vidējā, un tad atbilde vairs nav viena klase. Lineāra meklēšana, kas atgriežas pie pirmās sakritības, ir O(n) sliktākajā gadījumā un O(1), ja sakritība vienmēr ir pirmā; jautāt “to” sarežģītību būtu negodīgi. Binārā meklēšana ir izņēmums: tā iziet agri un joprojām ir tieši O(log n).
Vai sērijai ir nozīme?
Jā. Katra otrā pareizā atbilde pēc kārtas palielina to, cik dod nākamā, līdz griestiem, tāpēc tīrs brauciens ir vērts ievērojami vairāk nekā četras pareizas un divas nepareizas. Nepareiza atiestata sēriju.