Big-O Notasyonu nedir?

Yazdığınız bir programın neden bu kadar uzun sürdüğünü hiç merak ettiniz mi? Belki de kodunuzu daha verimli hale getirip getiremeyeceğinizi bilmek istersiniz. Kodun nasıl çalıştığını anlamak, kodunuzu bir sonraki seviyeye taşıyabilir. Big-O notasyonu, kodunuzun gerçekte ne kadar verimli olduğunu hesaplamak için kullanışlı bir araçtır.

Big-O Notasyonu Nedir?

Big-O gösterimi, kodunuzu çalıştırmanın ne kadar süreceğini hesaplamanın bir yolunu verir. Kodunuzun çalışmasının ne kadar süreceğini fiziksel olarak zamanlayabilirsiniz, ancak bu yöntemle küçük zaman farklarını yakalamak zordur. Örneğin, 20 ile 50 satır kod çalıştırma arasında geçen süre çok azdır. Ancak, büyük bir programda bu verimsizlikler artabilir.

Big-O gösterimi, bir algoritmanın verimliliğini ölçmek için kaç adım yürütmesi gerektiğini sayar. Verimliliği artırmak için kodunuzu ayarlamanız gerekiyorsa, kodunuza bu şekilde yaklaşmak çok etkili olabilir. Big-O gösterimi, algoritmaların verimliliğini çalıştırmak ve nesnel olarak karşılaştırmak için gereken adım sayısına göre farklı algoritmaları ölçmenizi sağlar.

Big-O Gösterimini Nasıl Hesaplarsınız?

Bir çekmecede kaç tane çorap olduğunu sayan iki işlevi ele alalım. Her işlev, çorap çiftlerinin sayısını alır ve tek tek çorapların sayısını döndürür. Kod Python'da yazılmıştır, ancak bu adımların sayısını nasıl sayacağımızı etkilemez.

Algoritma 1:

def sockCounter (numberOfPairs):
IndividualSocks = 0
aralıktaki x için (numberOfPairs):
IndividualSocks = IndividualSocks + 2
IndividualSocks döndür

Algoritma 2:

def sockCounter (numberOfPairs):
dönüş numarasıÇiftler * 2

Bu aptalca bir örnek ve hangi algoritmanın daha verimli olduğunu kolayca anlayabilmelisin. Ancak pratik yapmak için her birini inceleyelim.

İLİŞKİLİ: Programlamada İşlev Nedir?

Programlamada İşlev Nedir?

Kendi kodunuzu nasıl programlayacağınızı öğreniyorsanız, hangi işlevlerin olduğunu anlamanız gerekir.

Algoritma 1'in birçok adımı vardır:

1. IndividualSocks değişkenine sıfır değeri atar.
2. İ değişkenine bir değerini atar.
3. İ'nin değerini numberOfPairs ile karşılaştırır.
4. IndividualSocks'a iki ekler.
5. IndividualSocks'un artan değerini kendisine atar.
6. İ'yi birer birer artırır.
7. Daha sonra (indiviualSocks - 1) ile aynı sayıda adım 3 ila 6 arasında geri döner.

Birinci algoritma için tamamlamamız gereken adım sayısı şu şekilde ifade edilebilir:

4n + 2

N kez tamamlamamız gereken dört adım var. Bu durumda n, numberOfPairs'in değerine eşit olur. Ayrıca bir kez tamamlanan 2 adım vardır.

Buna karşılık, algoritma 2'nin sadece bir adımı vardır. NumberOfPairs'in değeri ikiyle çarpılır. Bunu şu şekilde ifade ederiz:

1

Zaten açık değilse, algoritma 2'nin biraz daha verimli olduğunu şimdi kolayca görebiliriz.

Big-O Analizi

Genel olarak, bir algoritmanın Big-O gösterimi ile ilgilendiğinizde, genel verimlilikle daha çok ilgilenirsiniz ve adım sayısının ince taneli analiziyle daha az ilgilenirsiniz. Gösterimi basitleştirmek için, sadece verimliliğin büyüklüğünü belirtebiliriz.

Yukarıdaki örneklerde, algoritma 2, bir olarak ifade edilecektir:

O (1)

Ancak algoritma 1 şu şekilde basitleştirilecektir:

O (n)

Bu hızlı anlık görüntü bize birinci algoritmanın verimliliğinin n'nin değerine nasıl bağlı olduğunu anlatıyor. Sayı ne kadar büyükse, algoritmanın tamamlaması gereken adım o kadar fazladır.

Doğrusal Kod

N'nin değerini bilmediğimiz için, n'nin değerinin çalıştırılması gereken kod miktarını nasıl etkilediğini düşünmek daha yararlıdır. Algoritma 1'de ilişkinin doğrusal olduğunu söyleyebiliriz. Adımların sayısını ve n'nin değeri yükselen düz bir çizgi elde edersiniz.

İkinci Dereceden Kod

Tüm ilişkiler doğrusal örnek kadar basit değildir. Bir 2D diziniz olduğunu ve dizide bir değer aramak istediğinizi hayal edin. Bunun gibi bir algoritma oluşturabilirsiniz:

def searchForValue (targetValue, arraySearched):
foundTarget = Yanlış
Aranan dizideki x için:
x cinsinden y için:
eğer (y == targetValue):
foundTarget = Doğru
iade bulundu

Bu örnekte, adımların sayısı arraySearched'deki dizi sayısına ve her dizideki değerlerin sayısına bağlıdır. Dolayısıyla, basitleştirilmiş adım sayısı n * n veya n² olacaktır.

Bu ilişki ikinci dereceden bir ilişkidir, yani algoritmamızdaki adım sayısı n ile üssel olarak artar. Big-O gösteriminde şu şekilde yazarsınız:

O (n²)

İLİŞKİLİ: CSS Dosyalarını Kontrol Etmek, Temizlemek ve Optimize Etmek İçin Kullanışlı Araçlar

Logaritmik Kod

Başka birçok ilişki olmasına rağmen, bakacağımız son ilişki logaritmik ilişkilerdir. Hafızanızı yenilemek için, bir sayının günlüğü, bir taban verilen bir sayıya ulaşmak için gereken üs değeridir. Örneğin:

günlük 2 (8) = 3

Günlük üçe eşittir çünkü tabanımız 2 olsaydı, 8 sayısına ulaşmak için üs değerinin 3 olması gerekirdi.

Dolayısıyla, logaritmik bir fonksiyonun ilişkisi, üstel bir ilişkinin tersidir. N arttıkça, algoritmayı çalıştırmak için daha az yeni adım gerekir.

İlk bakışta, bu mantıksız görünüyor. Bir algoritmanın adımları n'den daha yavaş nasıl büyüyebilir? Buna güzel bir örnek ikili aramalardır. Benzersiz değerler dizisindeki bir sayıyı aramak için bir algoritma düşünelim.

• En küçüğünden en büyüğüne sırayla aramaya bir dizi ile başlayacağız.
• Ardından, dizinin ortasındaki değeri kontrol edeceğiz.
• Numaranız daha yüksekse, aramamızdaki düşük sayıları hariç tutacağız ve sayı daha düşükse, daha yüksek sayıları çıkaracağız.
• Şimdi kalan sayıların ortasındaki sayıya bakacağız.
• Yine, hedef değerimizin orta değerden yüksek veya düşük olmasına bağlı olarak sayıların yarısını hariç tutacağız.
• Hedefimizi bulana veya listede olmadığını belirleyene kadar bu işleme devam edeceğiz.

Gördüğünüz gibi, ikili aramalar her geçişte olası değerlerin yarısını ortadan kaldırdığından, n büyüdükçe, diziyi kontrol etme sayımız üzerindeki etki neredeyse hiç etkilenmez. Bunu Big-O gösterimiyle ifade etmek için şunu yazacağız:

O (günlük (n))

Big-O Gösteriminin Önemi

Big-O ulus size bir algoritmanın ne kadar verimli olduğunu iletmenin hızlı ve kolay bir yolunu sunar. Bu, farklı algoritmalar arasında karar vermeyi kolaylaştırır. Bir kitaplıktan bir algoritma kullanıyorsanız ve kodun neye benzediğini tam olarak bilmiyorsanız, bu özellikle yararlı olabilir.

Kodlamayı ilk öğrendiğinizde, doğrusal fonksiyonlarla başlarsınız. Yukarıdaki grafikten de görebileceğiniz gibi, bu sizi çok uzağa götürür. Ancak daha deneyimli hale geldikçe ve daha karmaşık kodlar oluşturmaya başladıkça, verimlilik bir sorun olmaya başlar. Kodunuzun verimliliğini nasıl ölçeceğinizi anlamak, size onu verimlilik için ayarlamaya ve algoritmaların artılarını ve eksilerini tartmaya başlamanız için gereken araçları verecektir.

En Yaygın 10 Programlama ve Kodlama Hatası

Kodlama hataları pek çok soruna yol açabilir. Bu ipuçları, programlama hatalarından kaçınmanıza ve kodunuzu anlamlı tutmanıza yardımcı olacaktır.

Yazar hakkında