Chewy Mesaj tarihi: Aralık 5, 2011 Mesaj tarihi: Aralık 5, 2011 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 Mesaj tarihi: Aralık 5, 2011 Mesaj tarihi: Aralık 5, 2011 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 Mesaj tarihi: Aralık 5, 2011 Mesaj tarihi: Aralık 5, 2011 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 Mesaj tarihi: Aralık 5, 2011 Mesaj tarihi: Aralık 5, 2011 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 Mesaj tarihi: Aralık 5, 2011 Konuyu açan Mesaj tarihi: Aralık 5, 2011 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 Mesaj tarihi: Aralık 5, 2011 Mesaj tarihi: Aralık 5, 2011 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 Mesaj tarihi: Aralık 5, 2011 Mesaj tarihi: Aralık 5, 2011 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
Öne çıkan mesajlar