Büyük o gösterimi

[mulgear6]

ya bi türlü çözemedim adam gibi şu konuyu

http://tr.wikipedia.org/wiki/B%C3%BCy%C3%BCk_O_g%C3%B6sterimi

şunun





mesela

n^2 + n € O(n^2) dediginde bunu nası çözüyoruz
sinir oldum örnek de koymamıslar geçen dönem de bi göz atmıştım sadece kaldıydım zaten konunun oldugu sınavdan şimdi algo dersinde de çıktı bi iki örnek filan koyun yada koyıyım bakalım edelim ne güzel

[mulgear6]

up

[Fly]

n^2 + n ∈ O(n^2) cozulu ki, nkare arti n in mevzubahis klasmana girdigini soyluyor

edit :
ha kanit
n^2 + n <= 2n^2 , n tane eleman uzerinde calisacak bir algoritma icin

ozetle big o (O(X)) dedigin sey bir noktadan sonra X ile ayni gelisimi gosteren bir baska ifade tarafindan sinirlandigini belirtiyor
misal n eleman uzerinde islem yapan su algoritma worst case O(nlogn) komplekslikte dedigin vakit en vahim kosullarda nlogn egrisi dogrultusunda bir gelisimi olacak demek sen eleman sayisini arttirdikca

edit3:
dedigim ornek biraz yanlis olmus, daha dominant bir ifade tarafindan sinirlandigini biliyorsan onu yazar insanlar
yani n^3logn + n^2 ise O(n^3logn) demek bu. O(n^2)
O(n^2) ∈ O(n^3) ayni zamanda da. daha zayif bir kume daha dominant olanin icinde

little o (o(x)) ise bunun biraz tersi gibi yanlis oldu, daha da agir olani gibi. sozkonusu ifade bunun yaninda tatava, cok ufak kaliyor manasinda
misal cok ufak bir dt degeri icin dt^2 ∈ o(dt)

[Fly]

big o disinda da acikcasi makaleler disinda omegayi cok kullanan gormedim hele ki normal lisans seviyesinde, soruyorlar mi ki sinavda

[mulgear6]

istiyosan bi gösteriyim geçen dönemden beriki skriptleri :D

[mulgear6]

Fly said:

big o disinda da acikcasi makaleler disinda omegayi cok kullanan gormedim hele ki normal lisans seviyesinde, soruyorlar mi ki sinavda

ha bii de mantıgını biliyorum olayın da
çözemiyorum sorularını filan

[Deacon]

Berk sen master theorem ogrensen yeter. Gerisine kasma sdf.

[Fly]

aynen mastir teorem var bir pratikte kullandiklarimdan aklimda kalan,
ne soruyorlar ki

[mulgear6]

şimdi yatıcam skriptleri filan ssleyip koymaya usendim de master theorem geçen dönem vardı bu dönem algo dersinde sortların T (ne diyosa siz barbar türkler ona) kısmıyla alakalı hep O lular var
sorularını çözemiyorum (özellkle omegalı ve dolayısıyla w lu olanlarını) o konuda çözüm desteği arıyodum

sınavda muhtemelen şu tarz bişeyler gelicek

log n 2 O(n2) 4 Richtig. Falsch, richtig ware: log n 2 O( )
log n 2 o(n) 4 Richtig. Falsch, richtig ware: log n 2 o( )
log n 2 OMEGA (1) 4 Richtig. Falsch, richtig ware: log n 2
( )
log n 2 (n^n) Richtig. 4 Falsch, richtig ware: log n 2 ( log n )
b)


c/p yaptım aradaki 2 ler € olucak

onun dısında ezber zaten ya geri kalan sort tiplerinin Tleri

[Fly]

ja wunderbar

dogru mu ? yanlissa yanina dogrusunu yaz
mi diyor

oyle oldugunu varsayarak

1.
logn E O(n^2) dogru
n^2 veya n'in logn' den daha dominant oldugunu goz onune alarak

|logn| <= |n| <= |n^2|
dolayisiyla O(n^2)
kabaca ifadendeki en dominant/hizli artan ifadenin cinsine ait oluyor

2.
logn n'den her an daha zayif demek bu
logn/n limiti n sonsuza giderken sifir ise
1/n * -1/n^2 = 0

protip : peki O(n) midir deseydi little o big o'nun alt kumesi dolayisiyla evet diyecektin

3.
omega big o'nun tersi gibi, logn 1'den bir noktadan sonra daha hizli bir gelisim gosterir mealinde
kacirdigim bir nokta yoksa logn >= baya asikar n yeterince buyudukce

4.
logn n^n in kendisi degil, asikar bu da sanki

[Deacon]

Abi sen bunlarin ne ise yaradigini anladin mi? Algoritmadan once diskrit matematikte gosterirler zaten big oh'yu. Sonra algoritmada ne oldugundan cok uygulamasina yonelmeleri lazim. Wiki sayfasindan falan iyice otur ogren bence. Fonksiyonlari ustten ve alttan boundlamak baya basit bi konsept yani.