Można wyznaczyć 2 złożoności algorytmu:
Dokładna - rzadko się używa
Notacja dużego O - jest to taka funkcja, która jest zawsze wyżej niż złożoność dokładna algorytmu.
To co przedstawiłeś na swoim wykresie, to właśnie złożoność dokładna. Taką złożoność opisuje się w dwóch przypadkach danych:
Dane pesymistyczne - najgorszy możliwy układ danych
Dane optymistyczne - najlepszy możliwy układ danych
Czasami algorytmy nie posiadają takiego podziału w zależności od danych.
Wróćmy do tej notacji dużego O. Twój wykres przedstawia zależność czasu od ilości danych. Jest to jakaś tam funkcja. Jakby się uprzeć, to może i wyprowadzisz wzór funkcji maksymalnie zbliżonej do Twojego wykresu, ale informatykom nie jest to potrzebne. Przedstawianie złożoności algorytmów za pomocą skomplikowanych wzorów utrudniłoby porównywanie takich algorytmów. Stworzono więc notację dużego O.
Notacja dużego O jest to taka funkcja fundamentalna, która jest zawsze nad wykresem wykonywania Twojego programu dla danych pesymistycznych. To znaczy, że niezależnie jakie dane wprowadzisz do algorytmu opisanego wzorem: O(n), to Twój algorytm zawsze wykona mniej lub tyle samo operacji ile danych.
Aby lepiej Ci pokazać czym jest notacja dużego O i jak zależna jest od programisty, to taki przykład:
void algorytm()
{
int zmienna = 5;
}
Załóżmy, że utworzenie zmiennej i wpisanie do niej wartości, to jedna operacja. Złożoność tego algorytmu? Dokładna, to oczywiście 1. Zawsze będzie jedna operacja. A notacja dużego O, to taka funkcja, która zawsze będzie równo lub nad. W takim razie dla tego algorytmu poprawne są notacje: O(1), O(n), O(log), O(n^2), O(2^n). Z czego tej pierwszy jest najbardziej trafny, ale zgodnie z definicją notacji dużego O, wszystkie są poprawne.
Teraz posłużę się Twoim obrazkiem z moją drobna edycją w paitcie :-D
Jak widać funkcja O(n^2) jest zawsze nad Twoją złożonością czasową. Zatem za pomocą O(n^2) możesz opisać złożoność czasową swojego algorytmu.
Myślę, że już wiesz o co chodzi z tymi "O"
Pozdrawiam :-)