MODUŁ 09

Złożoność i zadania integrujące

Testowanie poprawności i analiza złożoności to dwie różne rzeczy. Funkcja może zwracać dobry wynik dla małych przykładów, ale być zbyt wolna dla dużych danych.

W skrócie

Testowanie poprawności i analiza złożoności to dwie różne rzeczy. Funkcja może zwracać dobry wynik dla małych przykładów, ale być zbyt wolna dla dużych danych.

Typowe punkty odniesienia:

jeden przebieg po n elementach: zazwyczaj O(n);
dwie zagnieżdżone pętle po n elementach: często O(n²);
dzielenie problemu na połowę w każdym kroku: często O(log n);
pełny przegląd każdej pary elementów: często O(n²).

To tylko wskazówki: złożoność należy uzasadnić dla konkretnego algorytmu. W testach używaj danych większych od przykładów, a w kryterium punktowym podawaj oczekiwany rząd złożoności i ograniczenia wejścia.

Przykład

Największa suma spójnego fragmentu jednym przebiegiem.

long long najlepsza(const std::vector<long long>& v) {
    long long best = v[0], cur = v[0];
    for (int i = 1; i < (int)v.size(); ++i) {
        if (cur < 0) cur = v[i];
        else cur += v[i];
        if (cur > best) best = cur;
    }
    return best;
}

Bieżący fragment resetuje się, gdy zejdzie poniżej zera.
Wynik może być ujemny — nie wolno startować od zera.

Mierz na dużych danychMałe przykłady przechodzi i kwadratowe rozwiązanie — limit kroków je rozróżnia.

Złożoność i zadania integrujące

W skrócie

Przykład

Ćwiczenia

Sprawdzian III — moduły 7–9 (9 nowych zadań)