• bir algoritmanın girilen n büyüklügündeki input icin calisma süresini belirtmede kullanılan gösterim bicimi.
    mesela quicksort ortalama o(n)=n log n zamanda calisir...
  • (bkz: order of n)
  • binary search denen algoritmayi b fonksiyonu olarak ele alirsak..

    o(b(n)) = log n

    seklinde gosterilir. yani bu arkadas parametre olarak fonksiyon alan bir fonksiyondur. ayrica:

    k sabit olmak uzere..
    o(x(n)) = k log n = log n
    dir cunku n < k aninda k in onemi olmasina ragmen n > k durumunda hic onemi yoktur cunku n in sonsuza kadar yolu vardir.
  • o(n3 + 5n2 + n +56) ile o(n3) e$ittir bu notation'da.
  • bilgisayar biliminde karmasiklik analizinde kullanilan bir gosterimdir. bu gosterimde sabit katsayilar yok sayilir.
    tam olarak soylenmesi gerekirse bir algoritmanin asimtotik calisma suresinin ust limitidir. bu nedenle bir algoritma o(n2) ise ayni zamanda o(n3)'dur ama her o(n2) olan algoritma o(n) degildir. bundan daha kotu degildir anlamina gelir.
  • algoritmanin calisma karmasikliginin ust limitini belirler, bu yuzdende aslinda cok iyi bir gosterim sekli degildir. hesaplamasi kolay diye kullanilir.
    matematiksel gosterimi su sekildedir :
    f(n)<= ct(n) => f(n) c o(t(n)) denir.

    omega notation diye bir gosterim tarzi daha vardir, bu gosterim tarzi ise algoritmanin karmasikliginin alt limitini belirler.
    matematiksel gosterimi su sekildedir:
    f(n) >= ct(n) => f(n) c omega(t(n)) denir. kusura bakmayin elemanidir isareti ile omega isaretini cikartamadim.
    tabii buda tek basina algoritmanin karmasikligini cok net vermez.

    o zaman napalim demisler, bir algoritmanin hem alt limitini hem ust limitini verirsek iste o zaman tam olur demisler ve teta notation cikmis.
    buda
    d.f(n)<=t(n)<=c.f(n) olursa olur
    yani bir nevi omega ile big-oh un kesisim noktasi
  • bu konuyla ilgili ilk çalı$maları yapanlardan esinlenilerek, bachmann-landau notasyonu olarak da bilinir.
  • hangi arama, hangi siralama algoritmasini kullanmaliyim, benim icin önemli olan kriter zamansa ya da yerse hangisini secmeliyim gibi sorulara efektif yanitlar bulabilmek icin göz önünde bulundurulan, islem karmasikligi gösterimi. surada da bir cheat sheetmevcut: big o notation
hesabın var mı? giriş yap