Big-O — įvardyk kodo sudėtingumą
Perskaityk fragmentą, įvardyk jo laiko sudėtingumą, tada pažiūrėk augimo kreivę. Šešios klasės, šeši raundai. Nemokamai.
Penki fragmentai, penkios iš šešių sudėtingumo klasių, kiekviena klausiama po kartą.
Kaip žaisti
- Perskaityk fragmentą ir pasirink jo laiko sudėtingumą iš šešių.
- Augimo kreivė brėžiama po kiekvieno atsakymo: tavo raudona, teisinga žalia.
- Penkios iš šešių klasių per bandymą, be pasikartojimų, tad tas pats atsakymas teisingas daugiausia vieną kartą.
- Teisingi atsakymai iš eilės duoda daugiau. Klaidingas nunulina seriją.
Kaip tai veikia
Kiekvienas raundas parodo trumpą kodo gabalą ir klausia jo laiko sudėtingumo. Atsakai, ir nubrėžiama augimo kreivė — tavo prieš teisingą — tad pasirinkimas nustoja būti etiketė ir tampa forma, kurią matai. Vienas bandymas klausia penkias klases iš šešių, sumaišytas ir be pasikartojimų, tad atsakinėti visada tą patį teisinga daugiausia vieną kartą — o praleista klasė keičiasi, todėl paskutinis raundas niekada nebūna dovanotas atmetimo būdu. Fragmentai parinkti taip, kad kiekvienas turėtų vieną apginamą atsakymą: jokių ankstyvų išėjimų, jokių paslėptų bibliotekos kaštų ir nieko, kas išduotų savo paties sudėtingumą komentare. Rikiavimas visur laikomas O(n log n) — būtent tai duoda bet kuri standartinė biblioteka. Viskas veikia tavo įrenginyje, niekas niekur nesiunčiama, ir registruotis nereikia.
O žymėjimas aprašo, kaip auga kaina, o ne kokia ji. O(n²) su gerom konstantom įveikia išpūstą O(n log n) tuose dydžiuose, kuriuos mato dauguma tikro kodo — tam skirtas kitas šios svetainės žaidimas.
Dažnai užduodami klausimai
Kodėl kreivė logaritminiu masteliu?
Nes kitaip šešios klasės netelpa į vieną grafiką. Prie n=24 pastovaus laiko funkcija kainuoja 1, o eksponentinė — šešiolika milijonų, tad tiesinėje ašyje penkios iš šešių kreivių būtų ta pati plokščia linija apačioje. Logaritminis mastelis kiekvieną klasę paverčia atskiriamu nuolydžiu, ir būtent tai verta pamatyti.
Ar rikiavimas tikrai O(n log n)?
Palyginimo rikiavimams taip — tai įrodyta apatinė riba ir tai, ką duoda bet kuri standartinė biblioteka. Skaičiavimo ir skaitmeninis rikiavimas greitesni, nes nelygina, bet jiems reikia prielaidų apie raktus. Kai fragmentas čia kviečia sort(), tai kainuoja n log n.
Kodėl nėra fragmentų su ankstyvu išėjimu?
Nes ankstyvas išėjimas paverčia blogiausią atvejį vidutiniu, ir tada atsakymas nustoja būti viena klasė. Tiesinė paieška, grąžinanti prie pirmo atitikmens, yra O(n) blogiausiu atveju ir O(1), jei atitikmuo visada pirmas; klausti „to“ sudėtingumo būtų nesąžininga. Dvejetainė paieška yra išimtis: ji išeina anksti ir vis tiek yra tiksliai O(log n).
Ar serija svarbi?
Taip. Kas antras teisingas atsakymas iš eilės padidina tai, kiek duoda kitas, iki lubų, tad švarus bandymas vertas gerokai daugiau nei keturi teisingi ir du klaidingi. Klaidingas atsakymas seriją nunulina.