Big-O Notasyonu Nedir?

Big-O Notasyonu Nedir?

Yazdığınız bir programın çalışmasını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 düzeye 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 notasyonu, kodunuzu çalıştırmanın ne kadar süreceğini hesaplamanın bir yolunu sunar. 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ırmak arasında geçen süre çok küçüktür. Ancak, büyük bir programda bu verimsizlikler artabilir.



e-postaya bağlı hesapları ücretsiz bulun

Big-O notasyonu, 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 notasyonu, farklı algoritmaları çalıştırmak için gereken adım sayısına göre ölçmenizi ve algoritmaların verimliliğini objektif olarak karşılaştırmanızı sağlar.





Big-O Notasyonunu Nasıl Hesaplarsınız?

Bir çekmecede kaç tane çorap olduğunu sayan iki işlevi düşünelim. 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ım sayısını nasıl sayacağımızı etkilemez.

Algoritma 1:



def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Algoritma 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Bu aptalca bir örnek ve hangi algoritmanın daha verimli olduğunu kolayca söyleyebilmelisiniz. Ama pratik için, her birinin üzerinden geçelim.



İLGİLİ: Programlamada Fonksiyon Nedir?

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



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

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

4n + 2

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

Karşılaştırıldığında, algoritma 2 sadece bir adıma sahiptir. NumberOfPairs değeri iki ile çarpılır. Bunu şöyle ifade edeceğiz:

1

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

Büyük-O Analizi

Genel olarak, bir algoritmanın Big-O notasyonuyla 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, verimliliğin büyüklüğünü belirtebiliriz.

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

O(1)

Ancak algoritma 1 şu şekilde basitleştirilebilir:

O(n)

Bu hızlı enstantane bize algoritma 1'in verimliliğinin n değerine nasıl bağlı olduğunu anlatıyor. Sayı büyüdükçe, algoritmanın tamamlaması gereken daha fazla adım olacaktır.

Doğrusal Kod

İmaj Kredisi: Nick Fledderus/ İsim Proje

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ı olur. Algoritma 1'de ilişkinin doğrusal olduğunu söyleyebiliriz. Adım sayısı ile n değerini karşılaştırırsanız, yükselen düz bir çizgi elde edersiniz.

ikinci dereceden kod

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

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

Bu örnekte, adımların sayısı arraySearched içindeki dizilerin sayısına ve her dizideki değerlerin sayısına bağlıdır. Bu nedenle, basitleştirilmiş adım sayısı n * n veya n² olur.

resmin dpi'sini nasıl görebilirim

İmaj Kredisi: Nick Fledderus/ İsim Proje

Bu ilişki ikinci dereceden bir ilişkidir, yani algoritmamızdaki adım sayısı n ile üstel olarak büyür. Big-O notasyonunda şöyle yazarsınız:

O(n²)

İLGİ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. Belleğinizi 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:

log 2 (8) = 3

Günlük üçe eşittir, çünkü tabanımız 2 olsaydı, 8 sayısına ulaşmak için 3'lük bir üs değerine ihtiyacımız olurdu.

İmaj Kredisi: Nick Fledderus/ İsim Proje

Bu nedenle, 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 karşı-sezgisel görünüyor. Bir algoritmanın adımları nasıl n'den daha yavaş büyüyebilir? Buna iyi bir örnek ikili aramalardır. Bir dizi benzersiz değerde bir sayı aramak için bir algoritma düşünelim.

  • Aramaya küçükten büyüğe doğru bir dizi ile başlayacağız.
  • Ardından, dizinin ortasındaki değeri kontrol edeceğiz.
  • Numaranız daha yüksekse, daha düşük sayıları aramamıza, sayı daha düşükse daha yüksek sayıları hariç tutacağız.
  • Şimdi, kalan sayıların ortadaki sayısına 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ısı üzerindeki etki çok az etkilenir. Bunu Big-O notasyonunda ifade etmek için şunu yazardık:

O(log(n))

Big-O Notasyonunun Önemi

Big-O ulus, 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. Bu, özellikle bir kitaplıktan bir algoritma kullanıyorsanız ve kodun nasıl göründüğünü tam olarak bilmiyorsanız yararlı olabilir.

mevcut olduğunda donanım ivmesini kullanmak ne anlama gelir?

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ürecektir. Ancak daha deneyimli hale gelip 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, onu verimlilik için ayarlamaya başlamak ve algoritmaların artılarını ve eksilerini tartmak için ihtiyacınız olan araçları size sağlayacaktır.

Paylaş Paylaş Cıvıldamak E-posta En Yaygın 10 Programlama ve Kodlama Hatası

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

Sonrakini Oku İlgili konular
  • Programlama
  • Programlama
Yazar hakkında Jennifer Seaton(21 Makale Yayınlandı)

J. Seaton, karmaşık konuları ayrıştırma konusunda uzmanlaşmış bir Bilim Yazarıdır. Saskatchewan Üniversitesi'nden doktora derecesine sahiptir; Araştırması, öğrencilerin çevrimiçi katılımını artırmak için oyun tabanlı öğrenmeyi kullanmaya odaklandı. Çalışmadığı zamanlarda onu kitap okurken, video oyunları oynarken ya da bahçe işleriyle uğraşırken bulacaksınız.

Jennifer Seaton'dan Daha Fazla

Haber bültenimize abone ol

Teknik ipuçları, incelemeler, ücretsiz e-kitaplar ve özel fırsatlar için bültenimize katılın!

Abone olmak için buraya tıklayın