Witam! Jestem studentem drugiego roku...Muszę podać zlozoność obliczeniowa tego algorytmu:
Mam nadzieję, że ktoś pomoże...
0
0
O(k)
0
czyli po prostu O(n) ?
a jak to rozpoznac?
0
o_O? Proponuje zacząć od myślenia. Popatrz na ten algorytm i policz sobie ile razy operacje będą się wykonywać. Podpowiem ze masz tam tylko jedną pętlę od 0 do k...
0
dobrze...ale zlozonosci sie nie okresla liczbą "n"?
0
No to chyba logiczne, że nie zawsze masz jedną zmienną i to w dodatku o nazwie n. Dla przykładu, pomnożenie metodą naiwną dwóch macierzy o rozmiarach a x b i b x c ma złożoność obliczeniową Theta(abc).
0
Mam nadzieję że nie jesteś studentem 2 roku informatyki...
Jeśli za n przyjmiesz sobie rozmiar problemu, to tak, mozesz napisać ze złożonośc jest O(n). Skoro w przykładzie było to nazwane k to tak sobie to nazwałem.
No ale jak sie na to n uparłeś to jaką złożoność wg ciebie będzie miało to:
int n,k;
//wczytujemy n oraz k
for(int i=0;i<n;i++)
for(int j=0;j<k;j++)
//jakieśtam operacje
?
A jaką złożoność będzie miało:
int n;
//wczytujemy n
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
//jakieś operacje
?
0
Ilość wykonań (pesymistyczna):
- 1
- 1
- 1
- 1
- k - 1
- k - 1
- k - 1
- k - 1
- k - 1
Żadna funkcja nie jest wyższa od liniowej (lub inaczej - łączna liczba wykonań algorytmu, to 5k-1, czyli jest to funkcja liniowa) więc mamy złożoność O(k), a nawet theta(k), ponieważ złożoność optymistyczna (omega(k)) również jest funkcją liniową, ponieważ musimy sprawdzić każdy element.
W związku z tym, że funkcja theta implikuje funkcje omikron i omega to możemy powiedzieć, że ta funkcja jest dokładnie rzędu k (czyli właśnie theta(k)).
czyli [błąd ortograficzny] O(n) ?
a jak to rozpoznac?
Nie O(n), tylko O(k), ponieważ u ciebie ilość danych wejściowych to k. Przyjęło się, że jest to n i dlatego w złożoności zawsze występuje n, ale w twoim algorytmie jest k i nic nie szkodzi. A jak rozpoznać to masz wyżej.
0
Program wygląda tak...
