Złożoność obliczeniowa - udowodnij z definicji

Question

Witam,
mógłby mi ktoś wytłumaczyć jak mogę formalnie udowodnić poniższe przykłady?

Answer 1

W czym problem? Jeśli zna się definicję notacji duże O, to wszystko jest proste. Zna Pan definicję?

To ja może napiszę 1 przykład.

c) istnieją stałe C1,C2>0, że f1(n)<=C1*g1(n) dla dostatecznie dużych n oraz f2(n)<=C2*g2(n) dla d. d. n. Zatem

f1(n)*f2(n)<=C1*C2*(g1(n)*g2(n)) = C*(g1(n)*g2(n)) dla dostatecznie dużych n, więc f1*f2 jest O(g1*g2).

Comments

Pewnie wyjdę na debla ale znam definicję, a mimo to dalej nie wiem o co w tym zadaniu chodzi.
np w przykładzie a

f1(n)+f2(n)<=(c1*g1(n),c2*g2(n))= C*max(g1(n),g2(n)) dla dostatecznie dużych n, więc f1(n)+f2(n) = O(max(g1(n),g2(n))?

Takie coś wystarczy?

---

Chyba napisałeś przecinek zamiast znaku plusa.

f1(n)+f2(n)<=c1*g1(n)+c2*g2(n)<=max(c1*g1(n)+c2*g1(n),c1*g2(n)+c2*g2(n))=

= max((c1+c2)*g1(n),(c1+c2)*g2(n))=max(C*g1(n),C*g2(n)), zatem f1(n)+f2(n)=O(max(g1(n),g2(n)). Rozpisałem trochę dłużej niż Ty, na sam początek może warto. Nie wiem czy warto.

Nie pisz, że wyjdziesz na debila. Ważne, że próbujesz i się uczysz!

---

max(c1*g1(n)+c2*g1(n),c1*g2(n)+c2*g2(n))

Jeśli można zapytać - dlaczego w tym fragmencie g1 i g2 są mnożone przez obydwie stałe c1 i c2, a nie tylko jedną?

b) f1(n)+f2(n)<=c2*g2(n)... i nie wiem co dalej... ehh
za przykłady d) i e) nawet nie wiem jak się zabrać. 
e) c1*1 = O(1)?

---

Są mnożone przez obie, bo rozpisałem to bardzo długo, Ty od razu w myśli zrobiłeś c=c1+c2, ja to zrobiłem później.

 

b) f1(n)+f2(n)<=c1*g1(n)+c2*g2(n)<=(na mocy założenia b przy dostatecznie dużym n większym od k)<=(c1+c2)*g2(n)=c*g2(n). Zatem f1(n)+f2(n) są rzędu O(g2(n))

---

jak mogę zapisać punkt d skoro nie ma tam funkcji f(n)?
c1*g(n)+c2*g(n)<=(c1+c2)*g(n),=C*g(n)
Można tak zapisać, czy przekombinowałem?
a punkt e)
c*1=O(1)? no bo nie mogę chyba zapisać c*1<=1?

---

e): funkcja f jest tutaj funkcją stale równa C, zaś g jest równa 1. Oczywiście, dla każdej liczby rzeczywistej C istnieje liczba rzeczywista C', że C<C'*1, zatem C jest O(1).

d) jeśli f jest O(C*g(n)), to granica przy  n->infinity |f(n)/C*g(n)|<infinity, np. niech ta granica równa się A.

Wówczas granica przy n->infinity |f(n)/g(n)|=C*A<infinity nadal.

---

O Boże...
Dziękuję za poświęcony czas, chyba nie będzie mi dane tego zrozumieć.

---

VinVix, wejdź sobie w artykuł o tej notacji na choćby wikipedii i spokojnie przeczytaj przykłady, które tam są. Chodzisz na wykłady albo konsultacje do profesorów? To naprawdę nie jest trudne. Swoją drogą złożoność obliczeniowa, P-NP, algorytmy na różne rzeczy to naprawdę ciekawe zagadnienia, w przeciwieństwie do jakichś np. metod numerycznych.