Złożoność obliczeniową wyznacza się ręcznie, określając funkcję przyrostu czasu wykonania algorytmu w zalezności od rozmiaru problemu.
Możesz oczywiście mierzyć czas wykonania i pokazać to na wykresie, ale wtedy nie będziesz znał dokładnej funkcji.
A jak wyznaczyc taką funkcję? To już zalezy od przypadku i od algorytmu. Przykład:
for(int i=0;i<n;i++)
{
//jakies operacje wykonywane w stałym czasie
}
Takie cos ma złożoność O(n) bo zwiększenie rozmiaru problemu (czyli naszego n) k-razy spowoduje k-krotne zwiększenie czasu wykonania, czyli przyrost jest liniowy.
Taki algorytm:
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
//operacje wykonywane w stałym czasie
}
}
Ma złożoność O(n^2) co można łatwo udowodnić sumując ile razy operacje zostaną wykonane:
n+(n-1)+(n-2)...+1 = n*(n+1)/2 = (n2 + n)/2 a dalej korzystając z notacji O() bierzemy pod uwagę tylko wielomian najwyższego stopnia i pomijamy stałe czynniki, co daje nam O(n2)