Big-O — nazwij złożoność kodu
Przeczytaj fragment, nazwij jego złożoność czasową, potem obejrzyj krzywą wzrostu. Sześć klas, sześć rund. Za darmo.
Pięć fragmentów, pięć z sześciu klas złożoności, każda pytana raz.
Jak grać
- Przeczytaj fragment i wybierz jego złożoność czasową spośród sześciu.
- Krzywa wzrostu jest rysowana po każdej odpowiedzi: twoja na czerwono, właściwa na zielono.
- Pięć z sześciu klas na rozgrywkę, bez powtórzeń, więc ta sama odpowiedź jest trafna najwyżej raz.
- Kolejne poprawne odpowiedzi płacą więcej. Błędna zeruje serię.
Jak to działa
Każda runda pokazuje krótki kawałek kodu i pyta o jego złożoność czasową. Odpowiadasz, a krzywa wzrostu zostaje narysowana — twoja obok właściwej — więc wybór przestaje być etykietą i staje się kształtem, który widać. Rozgrywka pyta o pięć z sześciu klas, w losowej kolejności i bez powtórzeń, więc odpowiadanie zawsze tego samego jest trafne najwyżej raz — a pominięta klasa się zmienia, przez co ostatnia runda nigdy nie wypada za darmo przez eliminację. Fragmenty dobrano tak, żeby każdy miał jedną obronną odpowiedź: bez wcześniejszych wyjść, bez ukrytych kosztów bibliotecznych i bez niczego, co zdradza własną złożoność w komentarzu. Sortowanie jest wszędzie liczone jako O(n log n), czyli tak, jak działa każda popularna biblioteka standardowa. Wszystko działa na twoim urządzeniu, nic nigdzie nie jest wysyłane i nie ma się gdzie rejestrować.
Notacja O opisuje, jak rośnie koszt, a nie ile wynosi. O(n²) z dobrymi stałymi bije rozdmuchane O(n log n) przy rozmiarach, które widzi większość prawdziwego kodu — to temat innej gry na tej stronie.
Najczęstsze pytania
Dlaczego krzywa jest w skali logarytmicznej?
Bo inaczej sześć klas nie zmieści się na jednym wykresie. Przy n=24 funkcja o czasie stałym kosztuje 1, a wykładnicza szesnaście milionów, więc na osi liniowej pięć z sześciu krzywych byłoby tą samą płaską linią przy dole. Skala logarytmiczna zamienia każdą klasę w rozróżnialne nachylenie, i to właśnie warto zobaczyć.
Czy sortowanie naprawdę jest O(n log n)?
Dla sortowań przez porównania tak — to udowodniona dolna granica i tak działa każda popularna biblioteka standardowa. Sortowanie przez zliczanie i pozycyjne są szybsze, bo nie porównują, ale wymagają założeń o kluczach. Kiedy fragment tutaj woła sort(), kosztuje to n log n.
Dlaczego nie ma fragmentów z wcześniejszym wyjściem?
Bo wcześniejsze wyjście zamienia przypadek pesymistyczny w średni i wtedy odpowiedź przestaje być jedną klasą. Wyszukiwanie liniowe zwracające przy pierwszym trafieniu jest O(n) w najgorszym przypadku i O(1), jeśli trafienie zawsze jest pierwsze — pytanie o „tę” złożoność byłoby nieuczciwe. Wyszukiwanie binarne to wyjątek: wychodzi wcześnie i nadal jest dokładnie O(log n).
Czy seria ma znaczenie?
Tak. Co druga poprawna odpowiedź z rzędu zwiększa to, ile płaci następna, aż do limitu, więc czysta rozgrywka jest warta znacznie więcej niż cztery trafione i dwie nietrafione. Błędna zeruje serię.