Złożoność czasowa

Uruchomienie programu zajmuje czas. Wiedza o tym, ile czasu to zajmuje, jest przydatna przy tworzeniu wydajnych programów. W programowaniu ilość czasu potrzebna na uruchomienie programu nazywa się złożonością czasową.

 Na przykład

for(int i=0;i<5;i++{
   cout<<i<<endl;
}

W powyższym przykładzie pętla wykonuje pięć iteracji, dlatego złożoność czasowa wynosi 5. Krótko mówiąc, złożoność czasowa odnosi się do liczby iteracji wykonywanych przez program. Jeśli program wykonuje jedną iterację, złożoność wynosi jeden, ale jeśli wykonuje dowolną liczbę n iteracji, złożoność czasowa wynosi n.

Złożoność czasową przedstawia się za pomocą notacji dużego O, a w tej notacji nigdy nie zapisujemy stałych wartości. Na przykład pięć lub sześć iteracji zapisuje się jako O(1), natomiast N iteracji lub 2N iteracji zapisuje się jako O(N). Analizując złożoność czasową programu, bierzemy pod uwagę najgorszy przypadek i obliczamy, ile iteracji może on wykonać.

W tym kursie musimy zrozumieć znaczenie złożoności czasowej oraz poznać kilka jej rodzajów. Omówimy je w następnej lekcji.

Przeczytaj poniższy artykuł, aby dowiedzieć się więcej o analizie złożoności czasowej.

Złożoność czasowa