MATLAB - złożoność obliczeniowa

Witajcie,
z góry przepraszam za [prawdopodobnie laickie] pytanie , ale jestem zielony w temacie;)

Otóż mam w MATLABie zaimplementowany algorytm i muszę do niego wyznaczyć funkcję złożoności obliczeniowej i przedstawić zależność na wykresie. Niestety nie mam pojęcia jak się za to zabrać.

Czy byłby ktoś tak miły i wytłumaczył mi to?

z góry dzięki.

Czytałeś Wiki?

Załóżmy, że funkcja f(n) określa optymistyczą, średnią lub pesymistyczną ilość instrukcji wykonywanych dla wejścia o rozmiarze n. Twoim zadaniem jest znalezienie: http://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu dla tej funkcji. Dostaniesz wtedy optymistyczną, średnią lub pesymistyczną (odpowiednio) złożoność.

Np jeżeli f(n) należy do O(n^{2), to po narysowaniu f(n) na wykresie, dla dostatecznie dużych n, funkcja f(n) będzie wyglądać mniej więcej jak funkcja c * n}2 dla pewnej stałej c.

Uwaga:
O(f(n)) jest w rzeczywistości zbiorem (tu: zbiorem funkcji asymptotycznie nie większych niż f(n)). Na Wiki jest jednak napisane np:
f(n) = O(f(n))
Jest to nieścisłość, ale tak często stosowana, że przymyka się na to oko. W rzeczywistości powyższy zapis oznacza:
f(n) należy do O(f(n))

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 = (n^{2 + 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(n}2)