Złożoność algorytmów

Często słyszy się o "złożoności algorytmu", "złożoności czasowej" lub "notacji duże-O" określając wydajność algorytmu, lecz czym tak naprawdę to jest?

Najprościej mówiąc, złożoność algorytmu to notacja, która określa jak jego czas wykonania rośnie zależnie od wielkości podanego zbioru (lub pojedynczego parametru, którego wartość ma wpływ na czas wykonania algorytmu).

Przyjęło się że tą wielkość określamy małą literką n. Gdy więcej niż jeden parametr lub wielkość ma wpływ na złożoność algorytmu, używa się innych małych liter z alfabetu angielskiego. 

Przykładowy zapis złożoności algorytmu: $O(n)$, $O(\log n)$, $O(n^2)$, $O(n * m)$

Kiedy dwa algorytmy mają tą samą złożoność, oznacza to tylko, że ich czas wykonania rośnie proporcjonalnie do siebie, ale nie znaczy to że są tak samo szybkie. O złożoności algorytmu można myśleć jak o mnożniku, który mnoży podstawowy czas wykonania. Łatwo można to zaobserwować w kodzie:

• Złożoność liniowa $O(n)$:

  for i in range(0, n):
  	// Pętla na każdym kroku wykonuje czynność która zajmuje 1ms

  Możemy przyjąć że podstawowy czas wykonania naszego algorytmu (pętli) to 1ms. Pętla wykona się n razy, zatem końcowy czas wykonania to $1ms * n$.

Złożoność łatwo zobrazować graficznie:

• Oś X określa wartość n. 
• Oś Y pokazuje ile razy wzrośnie czas wykonania algorytmu zależnie od n. 

Zobrazowane w kalkulatorze graficznym Desmos.