Algorytm o złożoności obliczeniowej czasowej O(n*n)

Question

Witam, potrzebuje trzech przykładów algorytmów, które mają poszczególne złożoności obliczeniowe czasowe: Algorytm o złożoności obliczeniowej czasowej rzędu O(1). Algorytm o złożoności obliczeniowej czasowej rzędu O(n). Algorytm o złożoności obliczeniowej czasowej rzędu O(n*n). Do każdego algorytmu należy dodać opis analizy jego złożoności. Liczę na Waszą pomoc bo nie wiem jak się do tego w ogóle zabrać  :)

Answer 1

O(1) => możemy obliczyć sumę wyrazów n-elementowego ciągu arytmetycznego jeśli skorzystamy ze znanego wzoru S = (a1+an)/2*n. Widać tu, że niezależnie od ilości wyrazów w ciągu (n) wykonamy tylko jedną operację (złożoność stała).

O(n) => możemy wykorzystać ten sam przykład co wyżej tylko, że realizujemy go za pomocą pętli, która przechodzi po wszystkich elementach. Widać, że zrobi to tyle razy, ile jest elementów ciągu (n), więc złożoność będzie liniowa.

O(n*n) => sortowanie bąbelkowe

Comments

a jak mam np. taki algorytm

 http://prntscr.com/fmi6jr

to jako parametr charakterystyczny biorę sume ? i jak to zapisać wtedy złożoność czasową ?

coś takiego czy źle to rozumie ?

suma=8 jest parametrem charakterystycznym

O(1)=1+1+1+1=4

O(1) jest dokładnie rzędu stałego 

??

Answer 2

O(1) wykonanie jakiegokolwiek wzoru.

O(n) np. liniowe przeszukiwanie całej tablicy.

O(n*n) np. Bubble sort.

Comments

A opis analizy złożoności jakoś jesteś w stanie mi objaśnić dla sortowania właśnie ?

---

Przy wyszukiwaniu liniowym mając n elementów w tablicy ograniczasz z góry przez O(n) ponieważ wykonujesz pętlę tylko raz. W Bubble sort wykonujesz pętlę w pętli. Dla każdego elementu tablicy porównujesz każdy element tej samej tablicy