Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Büyük O Notasyonu Nedir sorusuna cevap vermeye çalışacağız.
Büyük O Notasyonu Nedir?
Önceki yazımızda verimli algoritma ve faydalarından bahsetmiştik. Şimdi gelelim algoritmamızın verimini hesaplamaya. Eğer daha önceden O notasyonu hakkında makale okuduysanız, makalede bir çok teorik ve matematiksel bilgi olduğunu görmüşsünüz belki de sıkılıp kapatmışsınızdır. Bugün sizlere bu notasyonu fazla teorik bilgi vermeden ve sıkmadan, bizim işimize yarayacak kısmını anlatacağım.
Nasıl ki bir çok üründe, ürünün kalitesini göstermek için sayısal bir birim ve gösterim kullanılıyorsa (Pillerdeki mAh, işlemcilerdeki Ghz, ampullerdeki Watt vb.) aynı şekilde algoritmaların da bir kalite gösterimi vardır. İşte Büyük O Notasyonu tam olarak budur. Bir algoritma ne kadar verimliyse o kadar kalitelidir.
Büyük O Notasyonu Nasıl Hesaplanır?
Kısaca bir algoritmaya girdi olarak verilen verinin uzunluğu cinsinden yapılan işlem sayısıdır. En basit örneğinden N uzunluğundaki bir sayı dizisindeki elemanları toplamanın maliyeti N’dir yani O(n)’dir. Mesela kötü bir sıralama algoritması olan Bubble Sort O(n^2)’de çalışıyorken Merge Sort O(n * log n)’de çalışır. Buradan da anlayabiliriz ki Merge Sort, Bubble Sort‘dan daha verimli bir sıralama algoritmasıdır.
Büyük O Notasyonu Hakkında Somut Örnekler
Algoritma sorularında süre sınırı genelde 2 saniyedir. Yani algoritmanız problemi en fazla 2 saniye içinde çözmelidir. Çözümün daha fazla sürmesi halinde sorudan alacağınız puan 0’dır. 2 saniye de yaklaşık olarak 200 000 000 (200 milyon) işlem anlamına gelmektedir. Somut bir örnek vermem gerekirse 100 000 uzunluğundaki bir diziyi sıralamak için Bubble Sort kullanırsam maliyetim O(n^2) = 100 000 * 100 000 = 10 000 000 000 (10 milyar) olacaktır ve bilgisayarın 2 saniye içinde bunu çözmesi mümkün değildir. Ancak bunun yerinde Merge Sort kullansaydım maliyetim O(n * log n) = 100 000 * 16.6 = 1 660 000 olacaktır ve bilgisayar bu kadar işlemi salisiyeler içinde çözecektir.
Bir diğer verim unsurumuz da hafızadır. Algoritma sorularında hafıza (memory) sınırı 256 MB veya 512MB’dır. Sizin yazdığınız algoritmada hafızada yer kaplayan unsur tanımladığınız diziler ve değişkenlerdir. Bu tarz sorularda tanımlayabileceğiniz dizinin uzunluğu maksimum 256 MB için 67 000 000, 512MB için 134 000 000’dur. Yani bir problemi çözerken olabildiğince az boyutlarda dizi tanımlamamız gerek, bu nedenle bazı durumlarda dizide daha önce kullandığımız yerleri tekrar tekrar kullanmamız gerekebilir.
Şimdiden ileride öğreneceğimiz algoritmaların büyük O notasyonunda maliyet hesaplamalarını merak edenler varsa buradaki web sitesinden faydalanabilirler.
Bu günlük bu kadar arkadaşlar. Farkındayım biraz kısa bir yazı oldu ancak bu yazıyı bol bol teorik bilgi ve formülle doldurmak yerine biraz yüzeysel anlatıp ilerde soru çözerken veya algoritma analizi yaparken, yani büyük O notasyonunu kullandığımız zaman daha iyi anlayacağınızdan eminim. Mutlaka sorularınız vardır. Aşağıdan veya Soru Cevap bölümünde sormaktan çekinmeyin lütfen. Bir sonraki yazımızda ilk algoritmamız ile yolumuza devam edeceğiz. İyi çalışmalar.
Tüm Algoritma Derslerimiz İçin tıklayınız.
34