Big O notasyonu proof yardım yardım yardım

[Chewy]

Ya çıldırcam, anlayamadım nasıl , neye göre proof yapıyoruz bu big o da fln.


şimdi elimde 3n^2 + 6n is O(n^2) diye bir soru var.

Ben bunun proofunu nasıl yaparım? hangi mantıkla ? neyi nasıl kullanıcam?Kanıt yaparken hepsinde kullandığımız klasik bir şey mi var ?

[SpiderS_DangeR]

lim n sonsuza giderken yapıcaksın
yani n^2(3+6/n) den 6/n = 0 oluyo 3 de sabit olduğu için n^2

[barbu]

ben de unuttum ama algoritma kitaplarında yazar direk. oradan bir bak istersen. yoruma açık değil proof olayı ne de olsa. yanımdaysa ben de bir bakarım.

[Deacon]

Var abi klasik bir sey.

f(x) = O(g(x)) i ispatlamak istiyorsan:

f(x) <= cg(x)'i ispatlaman gerekiyor. kosullar da c>=1,x>=x0(x0 herhangi bir sabit).

http://en.wikipedia.org/wiki/Big_Oh#Formal_definition

Bak burda 2. sey benim yazdigim. Ornegi de var hemen altta.

[Chewy]

SpiderS_DangeR said:

lim n sonsuza giderken yapıcaksın
yani n^2(3+6/n) den 6/n = 0 oluyo 3 de sabit olduğu için n^2

şimdi kitapta t(n) <= cg(n) for all n => n0 bu ona mı çıkıyor ?

mesela gene kitapta

100n + 5 is O(n^2) diye bir soru vermiş.

100n + 5 <= 100n + n (for all n => 5) = 101n <= 101n^2 demiş

şimdi burda constant değer 5 mi yoksa n mi ? bunu böyle nasıl açabiliyor onu anlamadım ?

[Penthesilea]

abi senin kafan karismis, olay acmak degil burada tam tersine esitsizlik bulmak.

n sabit degil, degisken. deacon'un dedigi gibi f(x) = O(g(x)) i ispatlamak icin f(x) <= c g(x) i ispatlaman lazim.

verdigin ornek mesela:

100n + 5 = O (n^2) ispatla diyor.

100n + 5 <= 100n + n for n >= 5, bu tamam di mi? bunu kendimiz turettik, amacimiz boyle turetmeler yapa yapa en solda 100n + 5, en sagda ise n^2 birakmak. denklem cozmuyoruz, yaptigimiz sey en basitinden su: 3 5'ten kucukse, 5 de 6'dan kucukse, 3 6'dan kucuktur.

100n + 5 <= 100n + n (burada n=>5 sarti geldi) <= 101n <= 101n^2 (n>=5, c = 101)

[SpiderS_DangeR]

yok benim dediğim ispat değil pardon, fonksiyonun big oh'sunu hesaplamak.
ama şuraya bakabilirsin
http://www.cs.auckland.ac.nz/compsci220s1t/lectures/lecturenotes/GG-lectures/BigOhexamples.pdf