Złożoność algorytmu

[Matm]

Wiem że złożoność algorytmy zależy od konkretnego przypadku, ale jak określić kiedy złożoność algorytmu to
\(\displaystyle{ logN; N ^{2};N ^{N};N ^{m}}\) itp

[spajder]

Odpowiedź jest zawarta w samym pytaniu

złożoność algorytmy zależy od konkretnego przypadku

możesz pytać na przykładach

[PMichalak]

Jeśli zwiększysz dane dwukrotnie, a czas zwiększy się czteroktornie tzn, że \(\displaystyle{ T(n) = \Big_O(n^{2})}\)
Jeśli zwiększysz dwukrotnie, a czas zwiększy się jedynie o jakąś stałą tzn, że \(\displaystyle{ T(n) = \Big_O(log(n))}\)
Itd.

[limak1]

dobre założenia

[Matm]

a mógłby ktoś wypisac wszystkie te założenia?

[tkrass]

Nie wiem czy dobrze rozumiem pytanie, ale jeżeli tak, to musisz po prostu sprawdzić ile operacji wykona Twój program, na przykład jak napiszesz:

Kod: Zaznacz cały

int i=1;
while(i<=n) {
rób coś;
i++;
}

to algorytm ma złożoność liniową, a jak napiszesz:

Kod: Zaznacz cały

int i=1;
int k;
while(i<=n) {
k=1;
while(k<=n) {
rób coś;
k++;
}
i++;
}

to ma kwadratową. Jak puścisz np. pętlę po wszystkich i i w każdym jej wykonaniu będziesz robił wyszukiwanie binarne (które działa w czasie logarytmicznym), to dostaniesz złożoność \(\displaystyle{ O(n \log n)}\).
Czasami nie da się w tak prosty sposób określić złożoności programu, ale ogólnie musisz tylko sprawdzić ile wykonasz operacji w zależności od n.

[Matm]

jeżeli mam pętlę w pętli to mam \(\displaystyle{ N^{2}}\) jak trzy pętle w pętli to\(\displaystyle{ N^{m}}\) a jak mam jakaś pętlę np.
n=1
while n<10:
pokaż n; liniowa
n=n+1;

while:
k=1
while k<9: tutaj kwadratowa
pokaż k;
k++


to złożoność tego algorytmu
\(\displaystyle{ N^{m}}\)?