Dokładniej, należy napisać program, który wczytuje ciąg liczb całkowitych i wyznacza sumę elementów w takim maksymalnym fragmencie. Zadanie to można zinterpretować, na przykład, tak: dla określonego ciągu transakcji na koncie (wpłaty, wypłaty) chcemy wyznaczyć przedział czasu, w którym bilans transakcji był możliwie najkorzystniejszy.

Nasz ciąg najwygodniej reprezentować w tablicy. Pierwsze przychodzące na myśl rozwiązanie może polegać na przejrzeniu wszystkich fragmentów ciągu i sprawdzeniu, który z nich ma maksymalną sumę. W języku Pascal taka funkcja może wyglądać następująco:

Czy to jest dobre rozwiązanie? Można je chwilę potestować i stwierdzić, że dla kilku przykładów daje poprawne wyniki. Ale dobre to nie tylko znaczy poprawne. Czy ten program jest szybki? Sprawdźmy!

Na potrzeby tego zadania wygenerowaliśmy trzy testy zawierające ciągi o długościach 100 , 10 000 i 1 000 000. Gdy uruchamiamy na tych testach program oparty na powyższej funkcji, to na pierwszym z nich działa w ułamku sekundy, ale dla drugiego i trzeciego trudno doczekać się końca jego działania.

Nie trzeba było jednak uruchamiać tego programu, żeby domyślić się, że tak właśnie będzie. Spróbujmy ustalić, ile operacji wykonuje ten program dla danych wejściowych rozmiaru W programie występuje cała gama różnych operacji - przypisania, operacje arytmetyczne, warunki, pętle… - i trudno byłoby to tak dokładnie policzyć. Warto więc ustalić, która operacja jest operacją dominującą, czyli którą operację wykonujemy najczęściej - i tę operację zliczać. Łatwo zauważyć, że w tym przypadku będzie to zwiększanie wartości zmiennej suma. Ile razy ma to miejsce? Dla każdego fragmentu wykonujemy takich operacji, a zatem łącznie będzie ich:

Po pracowitym przeliczeniu tej sumy, którego oglądania darujemy Czytelnikowi, wychodzi:

Nietrudno teraz sprawdzić, że dla otrzymujemy, odpowiednio, mniej więcej i mniej więcej operacji. Biorąc pod uwagę, że obecnie komputery mogą wykonać maksymalnie bardzo prostych operacji na sekundę, widzimy, dlaczego nasz program działa tak wolno.

W takim razie warto zastanowić się nad tym, czy nie ma szybszego rozwiązania. Najbardziej znaczący składnik w powyższym wzorze to, oczywiście, składnik z i to on w decydującym stopniu wpływa na to, że nasz program działa tak wolno. Z tego względu w analizie liczby operacji wykonywanej przez program (czy raczej algorytm) pomija się składniki niższego rzędu, co w przypadku wielomianów oznacza, że interesuje nas tylko jednomian o najwyższym wykładniku. Dalszym uproszczeniem jest pominięcie, zazwyczaj niedużych, stałych czynników. W ten sposób uzyskujemy funkcję, która z niezłym przybliżeniem określa czas działania wynikowego programu. Powiemy więc, że nasz algorytm ma złożoność czasową Przykładowo, dla trzech podanych wartości funkcja przyjmuje wartości i co nieźle przybliża dokładnie obliczone liczby operacji. W dalszej części artykułu spróbujemy przekonać się, że pojęcie złożoności czasowej pomaga w projektowaniu szybkich programów.

Intuicyjnie złożoność wzięła się w powyższym programie stąd, że rozpatrujemy wszystkie fragmenty ciągu, których jest z grubsza i obliczamy sumę każdego z nich, co wymaga maksymalnie dodawań - łącznie, mniej więcej, dodawań. Gdyby dało się szybciej obliczać sumę fragmentu, udałoby nam się wykonywać jedynie mniej więcej operacji…

Okazuje się, że jest to możliwe. W rozwiązaniu przydaje się pomysł z zakresu księgowości: aby łatwo sprawdzać, na ile dobry był dany okres na koncie, wystarczy po każdej operacji przechowywać łączny bilans z wszystkich dotychczas wykonanych operacji. W ten sposób do określenia sumy danego okresu wystarczy nam znajomość bilansu na koniec tego okresu oraz bilansu tuż przed jego rozpoczęciem. Kod odpowiedniej funkcji znajduje się poniżej.

Zbadajmy, na ile szybkie jest to rozwiązanie. Uruchomienie go na naszych trzech testach wykazuje znaczącą poprawę: dla pierwszych dwóch testów wyniki otrzymujemy prawie natychmiast, choć dla trzeciego znów nie udaje się doczekać na odpowiedź. A co wykazuje analiza "teoretyczna"? Operacją dominującą będzie teraz dowolna z operacji wykonywanych wewnątrz dwóch zagnieżdżonych pętli. Każda z nich wykonywana jest tyle razy, ile jest możliwych wyborów indeksów czyli

razy, co odpowiada złożoności czasowej Obliczenia wstępne polegają na wykonaniu zaledwie dodawań, więc można je pominąć w opisie złożoności. Dla mamy zatem mniej więcej i operacji.

Nie moglibyśmy jednak tego wszystkiego pozostawić, nie przedstawiając rozwiązania, które poradzi sobie z naszym największym testem. Znów, intuicyjnie, złożoność czasowa powyższego rozwiązania bierze się stąd, że rozpatrujemy wszystkie początki i końce fragmentów, a każdych z nich jest Postawmy śmiałe pytanie: czy dałoby się zamiast tego rozważać np. tylko początki albo tylko końce fragmentów?… Okazuje się, że tak!

W tym celu wystarczy zapytać, jak dla ustalonego końca fragmentu dobrać początek fragmentu, tak aby suma fragmentu była maksymalna. Będzie to, oczywiście, taki indeks operacji, przed wykonaniem której bilans na koncie jest możliwie najmniejszy!

Tym razem główna pętla wykonuje jedynie kilka prostych operacji, więc standardowo z pominięciem stałej określamy złożoność czasową ostatecznego rozwiązania jako I rzeczywiście, jak można się już domyślić, to rozwiązanie bez problemu radzi sobie z wszystkimi trzema testami.

W tym artykule spróbowaliśmy w kilku słowach opowiedzieć, na czym polega analiza złożoności czasowej algorytmów. Celowo pominęliśmy kwestie takie jak dobór odpowiednich typów danych (czy typ LongInt wystarcza?) oraz złożoność pamięciową, czyli - znów przybliżone - określenie zużycia pamięci przez program.