Big O Notasyonu

Yazar: Leandro Alegsa Oluşturulma tarihi: 18 Mayıs 2022

Big O Notasyonu algoritmaları karşılaştırmanın bir yoludur. Ne kadar belleğe ihtiyaç duyulduğunu ve tamamlanması için ne kadar zaman gerektiğini hesaplayarak karşılaştırır.

Büyük O Gösterimi genellikle bir problemin ne kadar karmaşık olduğunu belirlemek için kullanılır ve problemin karmaşıklık sınıfı olarak da bilinir. Matematikçi Paul Bachmann (1837-1920), 1896 yılında "Analytische Zahlentheorie" adlı kitabının ikinci baskısında bu notasyonu kullanan ilk kişidir. Edmund Landau (1877-1938) bu gösterimi popüler hale getirmiştir. Bu nedenle insanlar Landau sembollerinden bahsederken bu gösterime atıfta bulunurlar.

Big O Notasyonu adını, fonksiyonların büyümesini ifade eden "fonksiyonun sırası" teriminden alır. Big O Notasyonu, fonksiyonun büyüme oranının üst sınırını (mümkün olan en yüksek miktarı) bulmak için kullanılır, yani girdiyi çıktıya dönüştürmek için gereken en uzun süreyi hesaplar. Bu, bir algoritmanın her seferinde en uzun yolun izleneceği en kötü durum senaryosunda ne kadar süre alabileceğine göre gruplandırılabileceği anlamına gelir.

Big O, en kötü durum senaryosu çalışma süresini bulan, bir algoritmanın programı bilgisayarda çalıştırmak zorunda kalmadan ne kadar verimli olduğunu gösteren bir ifadedir. Farklı bilgisayarlar farklı donanımlara sahip olabileceğinden ve bu nedenle tamamlamak için farklı sürelere ihtiyaç duyabileceğinden bu da kullanışlıdır. Big O her zaman en kötü durumu varsaydığı için tutarlı bir hız ölçümü gösterebilir: donanımınız ne olursa olsun, O ( 1 ) {\displaystyle O(1)} $O(1)$ her zaman O ( n ! ) {\displaystyle O(n!)} $O(n!)$ 'den daha hızlı tamamlanacaktır çünkü farklı verimlilik seviyelerine sahiptirler.

Örnekler

Aşağıdaki örneklerin hepsi Python ile yazılmış kodlar kullanmaktadır. Bunun Big O türlerinin tam listesi olmadığını unutmayın.

Sabit

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Girdiden bağımsız olarak her zaman aynı süreyi alır. Örneğin, bir tamsayı (x olarak adlandırılır) kabul eden ve değerinin iki katını döndüren bir işlevi ele alalım:

def double(x): return x * 2 #x çarpı 2 değerini döndürür

Girdiyi kabul ettikten sonra bu fonksiyon bir çıktı döndürmek için her zaman bir adım atacaktır. Her zaman aynı miktarda zaman alacağı için sabittir, bu nedenle O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Doğrusal

O ( n ) {\displaystyle O(n)} $O(n)$ . Girdinin boyutuna göre artar, n ile temsil edilir {\displaystyle n} . Bir fonksiyonun n sayısını kabul ettiğini ve 1'den n'ye kadar her sayıyı döndürdüğünü varsayalım:

def count(n): i = 1 #Değeri 1 olan "i" adında bir sayaç oluşturun while i <= n: #i, n'den küçük veya n'ye eşit olduğu sürece print(i) #i'nin değerini yazdır = i + 1 #i'yi "i + 1'in değeri" olarak yeniden tanımla

Eğer 5 değerini girecek olursak, bu 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} çıktısını verir. $1,2,3,4,5$ tamamlamak için 5 döngü gerekir. Benzer şekilde, 100 girersek 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ çıktısını verir ve tamamlanması için 100 döngü gerekir. Eğer girdi n {\displaystyle n} ise, algoritmanın çalışma süresi her seferinde tam olarak n {\displaystyle n} döngüdür, dolayısıyla O ( n ) {\displaystyle O(n)} 'dir. $O(n)$

Faktöriyel

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Faktöriyel miktarlarda artar, yani alınan süre girdiyle birlikte büyük ölçüde artar. Örneğin, dünya çapında beş şehri ziyaret etmek istediğimizi ve olası her sıralamayı (permütasyon) görmek istediğimizi varsayalım. Python'un itertools kütüphanesini kullanarak yazabileceğimiz bir algoritma aşağıdaki gibidir:

import itertools #Import the itertools library cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Seçtiğimiz şehirlerden oluşan bir dizi def permutations(cities): #Girdi olarak bir şehirler dizisi almak: for i in itertools. permutations(cities): #Öğelerimizin her bir permütasyonu için ("i" değişkenine atanmış) print(i) #Çıktı i

Bu algoritma, şehirlerimizin her bir benzersiz permütasyonunu hesaplayacak ve ardından çıktısını verecektir. Çıktı örnekleri şunları içerecektir:

('Londra', 'Paris', 'Berlin', 'Amsterdam', 'Roma') ('Londra', 'Paris', 'Berlin', 'Roma', 'Amsterdam') ('Londra', 'Paris', 'Amsterdam', 'Berlin', 'Roma') ... ('Roma', 'Amsterdam', 'Paris', 'Berlin', 'Londra') ('Roma', 'Amsterdam', 'Berlin', 'Londra', 'Paris') ('Roma', 'Amsterdam', 'Berlin', 'Paris', 'Londra')

Burada girdi listemiz 5 öğe uzunluğundadır ve her seçim için kalan seçeneklerimiz 1 azalır. Başka bir deyişle 5 girdimiz 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ öğelerini seçer (veya 5 ! {\displaystyle 5!} $5!$ ). Eğer girdimiz n {\displaystyle n} şehir uzunluğunda ise, o zaman çıktı sayısı n ! {\displaystyle n! } $n!$ ; başka bir deyişle, her permütasyondan geçtiğimizi varsayarsak, bunu tamamlamak için O ( n ! ) {\displaystyle O(n!)} $O(n!)$ döngüsüne ihtiyacımız olacaktır.

Little-o Notasyonu

Büyük O'nun daha katı bir versiyonu küçük O'dur. Büyük O ile little-o arasındaki fark, little-o'nun katı bir üst sınır olmasıdır: O ( n ) {\displaystyle O(n)} $O(n)$ tamamlanma süresinin girdi boyutuna bağlı olarak bu maksimuma çıkacağı anlamına gelirken, o ( n ) {\displaystyle o(n)} $o(n)$ tamamlanma süresinin genellikle bu sürenin altında olacağı anlamına gelir. Başka bir deyişle, Big O her döngünün en uzun yolu izleyeceğini ve sürecin mümkün olduğunca uzun süreceğini varsayarken, little-o gerçek çalışma süreleri konusunda daha gerçekçidir; döngü sayısı 6 yüzlü bir zarın atılmasına dayanıyorsa, Big O her zaman 6 atıldığını varsayarken, little-o diğer sayıların atılma olasılığını eşit olarak hesaba katacaktır.

Sorular ve Yanıtlar

S: Big O gösterimi nedir?

C: Big O notasyonu, farklı fonksiyonların büyüme oranlarını karşılaştırmanın bir yoludur ve genellikle tamamlanması için ne kadar bellek ve zaman gerektiğini hesaplayarak farklı algoritmaların verimliliğini karşılaştırmak için kullanılır. Bir problemin ne kadar karmaşık olduğunu belirlemek için de kullanılabilir.

S: Bu gösterimi ilk kim kullanmıştır?

C: Matematikçi Paul Bachmann (1837-1920) 1896 yılında "Analytische Zahlentheorie" adlı kitabında bu notasyonu ilk kullanan kişidir.

S: Büyük O ne anlama geliyor?

C: Büyük O, fonksiyonların büyüme oranını ifade eden "fonksiyonun mertebesi" anlamına gelir.

S: Büyük O nasıl kullanılır?

C: Big O notasyonu, fonksiyonun büyüme oranına bir üst sınır (mümkün olan en yüksek miktar) bulmak için kullanılır, yani bir girdiyi çıktıya dönüştürmek için gereken en uzun süreyi hesaplar. Bu, algoritmaların her seferinde en uzun yolun izleneceği en kötü durum senaryolarında ne kadar zaman aldıklarına göre gruplandırılabileceği anlamına gelir.

S: Landau sembolleri nedir?

C: Landau sembolleri, adını bu notasyonu popüler hale getiren Edmund Landau'dan (1877-1938) alan Big O notasyonunu ifade eder.

S: Büyük O neden kullanışlıdır?

C: Big O, her zaman en kötü durum senaryolarını varsaydığı ve bilgisayarlar arasındaki donanım farklılıklarından bağımsız olarak tutarlı hale getirdiği için bilgisayarlarda program çalıştırmak zorunda kalmadan hızı ölçmemizi sağlar. Ayrıca bir algoritmanın bilgisayarda çalıştırılmasına gerek kalmadan ne kadar verimli olduğunu gösterir.