Jump to content
  • entries
    16
  • comments
    0
  • views
    37,011

Big-Oh Notasyonu (O Notasyonu)


Doğuhan ELMA

101 views

Bilgisayar bilimlerinde, Big-Oh notasyonu (O notasyonu), bir algoritmanın performansını veya karmaşıklığını tanımlamak için kullanılır. Özellikle, bir algoritmanın en kötü durumdaki çalışma zamanını veya gereken hafıza alanını ifade eder. 

O notasyonu, algoritmanın girdi boyutuna (n) göre büyüme hızını belirtir. Örneğin, O(n) bir algoritmanın lineer zamanlı olduğunu belirtir: girdi boyutu iki katına çıktığında, algoritmanın çalışma süresi de yaklaşık iki katına çıkar. 

O( ) (Big O Notation): O büyük notasyonu, bir fonksiyonun büyüme oranının üst sınırını verir. Yani bir fonksiyonun ne kadar hızlı büyüdüğünün en kötü durumunu belirtir. Genellikle bir algoritmanın zaman veya alan karmaşıklığını belirtirken kullanılır.

Ω( ) (Big Omega Notation): Ω büyük notasyonu, bir fonksiyonun büyüme oranının alt sınırını belirtir. Yani bir fonksiyonun ne kadar hızlı büyüdüğünün en iyi durumunu ifade eder. Genellikle bir algoritmanın zaman veya alan karmaşıklığını belirtirken kullanılır.

θ( ) (Big Theta Notation): θ büyük notasyonu, bir fonksiyonun büyüme oranının hem üst sınırını hem de alt sınırını belirtir. Yani, bir fonksiyonun ne kadar hızlı büyüdüğünün ortalama veya tipik durumunu ifade eder. Genellikle bir algoritmanın zaman veya alan karmaşıklığını belirtirken kullanılır.

ω( ) (Little Omega Notation): ω küçük notasyonu, bir fonksiyonun büyüme oranının alt sınırını belirtir. Ancak, bu alt sınır özellikle n'in çok büyük olduğu durumlar için geçerlidir. Yani, bir fonksiyonun büyüme oranı n'nin belirli bir değerinden itibaren en azından belirli bir oranda büyür.

Bu sembollerin tümü asimptotik notasyonların bir parçasıdır ve genellikle algoritma karmaşıklığını ve performansını analiz ederken kullanılır. Her biri, bir fonksiyonun veya algoritmanın performansını farklı açılardan değerlendirmemize olanak sağlar.

 

Fonksiyonları En Basit Terimlerde Karakterize Etmek, fonksiyonları en basit ve anlaşılabilir haliyle ifade etmeyi ifade eder. Bu, genellikle bir fonksiyonun genel davranışını veya büyüme hızını ifade etmek için kullanılır.

Özellikle bilgisayar bilimlerinde ve algoritma analizinde, "Big O" (O büyük), "Big Omega" (Ω büyük) ve "Big Theta" (Θ büyük) notasyonları gibi asimptotik notasyonlar kullanılır. Bu notasyonlar, bir fonksiyonun büyüme hızını "en basit terimlerde" ifade ederler. Örneğin, bir fonksiyonun büyüme hızı doğrusal, logaritmik, karesel, kübik vb. olabilir.

Örneğin, bir algoritmanın zaman karmaşıklığını ifade ederken, genellikle en kötü durum senaryosunu (Big O), en iyi durum senaryosunu (Big Omega) ve ortalama durum senaryosunu (Big Theta) belirtiriz.

En basit terimlerle ifade etmek, genellikle sabit çarpanları ve daha küçük terimleri göz ardı etmeyi içerir. Örneğin, bir algoritmanın zaman karmaşıklığının 3n^2 + 2n + 1 olduğunu biliyorsak, genellikle bunu O(n^2) olarak ifade ederiz, çünkü n büyüdükçe n^2 terimi 2n ve 1 terimlerini domine eder.

Bununla birlikte, bu tür bir basitleştirme, yalnızca n'in yeterince büyük olduğu durumlarda doğru bir yaklaşımdır ve bazen daha detaylı bir analiz gerektirebilir. Fonksiyonları "en basit terimlerde" karakterize etmek, genellikle bir başlangıç noktasıdır ve daha detaylı bir analiz gerektirebilir.

Diğer bazı O notasyonları şunlardır:

- O(1): Sabit zamanlı. Algoritmanın çalışma süresi girdi boyutuna bakılmaksızın sabittir. 
- O(log n): Logaritmik zamanlı. Algoritmanın çalışma süresi, girdi boyutunun logaritmasına orantılıdır. İkili arama, O(log n) karmaşıklığa sahip bir örnektir.
- O(n log n): Lineer-logaritmik zamanlı. Çok sayıda popüler sıralama algoritması (örneğin, hızlı sıralama ve birleştirme sıralaması) genellikle bu karmaşıklığa sahiptir.
- O(n^2): Karesel zamanlı. Girdi boyutunun karesine orantılı olarak çalışır. Basit sıralama algoritmaları (örneğin, kabarcık sıralaması) genellikle bu karmaşıklığa sahiptir.
- O(n^3), O(n^4), ...: Kübik zamanlı, dördüncü derece zamanlı, vb. İç içe döngülerle bu tür karmaşıklıklar ortaya çıkar.
- O(2^n): Üssel zamanlı. Çalışma süresi, girdi boyutunun üssüne orantılı olarak artar. Böyle bir algoritma genellikle büyük girdiler için kullanışsızdır.
- O(n!): Faktöriyel zamanlı. Çalışma süresi, girdi boyutunun faktöriyeline orantılıdır. Seyahat satıcısı problemi gibi bazı problemler için naif çözümler genellikle bu karmaşıklığa sahiptir.

O notasyonu, genellikle algoritmanın en kötü durum performansını belirtir. Ancak bazen ortalama veya beklenen durum performansını belirtmek için de kullanılır. O notasyonu, farklı algoritmaların ve veri yapılarının performansını karşılaştırma ve analiz etme konusunda çok önemlidir.

1.png

Big-Oh notasyonu (O-notation), bir algoritmanın en kötü durum zaman karmaşıklığını belirtmek için kullanılır. Yani, bir algoritmanın maksimum çalışma süresini ifade eder.

Big-Oh notasyonu, bir fonksiyonun büyüme hızını karakterize etmeye yardımcı olur. Bu, genellikle bir algoritmanın performansını analiz etmek için kullanılır. Örneğin, bir algoritmanın çalışma süresi, girdi boyutuna (n) bağlı olarak lineer (n), logaritmik (log n), kuadratik (n^2), kübik (n^3), veya daha karmaşık bir biçimde artabilir.

Örneğin:

O(1) Notasyonu: Bu, bir algoritmanın süresinin her zaman sabit olduğunu gösterir. Yani, girdi boyutu ne olursa olsun, algoritmanın çalışma süresi değişmez. Aşağıdaki Python kodu, O(1) zaman karmaşıklığına bir örnektir:

def sabit_zaman(k):
    return k * k

O(n) Notasyonu: Bu, bir algoritmanın süresinin girdi boyutuyla doğru orantılı olarak arttığını gösterir. Aşağıdaki Python kodu, O(n) zaman karmaşıklığına bir örnektir:

def lineer_zaman(liste):
    for eleman in liste:
        print(eleman)

O(n^2) Notasyonu: Bu, bir algoritmanın süresinin girdi boyutunun karesiyle orantılı olarak arttığını gösterir. Aşağıdaki Python kodu, O(n^2) zaman karmaşıklığına bir örnektir:

def kare_zaman(liste):
    for i in liste:
        for j in liste:
            print(i, j)

Big-Oh notasyonu, algoritma tasarımında ve analizinde çok önemli bir rol oynar. Bu notasyon, farklı algoritmaların performanslarını karşılaştırmak ve en uygun algoritmayı seçmek için kullanılır.

Logaritmik zaman karmaşıklığı (O(log n)):

Bu tür algoritmalar, her adımda giriş verilerini bir faktörle azaltır. İkili arama algoritması bunun tipik bir örneğidir:

def binary_search(arr, low, high, x): 
    if high >= low: 
        mid = (high + low) // 2
        if arr[mid] == x: 
            return mid 
        elif arr[mid] > x: 
            return binary_search(arr, low, mid - 1, x) 
        else: 
            return binary_search(arr, mid + 1, high, x) 
    else: 
        return -1

Kuadratik zaman karmaşıklığı (O(n^2)):

Bu tür algoritmalar, genellikle iç içe döngüler içerir. İki boyutlu bir listeyi dolaşan veya basit sıralama algoritmaları (bubble sort, insertion sort vb.) kuadratik zaman karmaşıklığına örnek olarak verilebilir:

def bubble_sort(liste):
    n = len(liste)
    for i in range(n):
        for j in range(0, n - i - 1):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]

Kübik zaman karmaşıklığı (O(n^3)):

Bir algoritmanın çalışma süresi girdinin kübüne orantılıysa, bu algoritmanın karmaşıklığı O(n^3) olarak ifade edilir. Matris çarpımı, tipik bir O(n^3) algoritmasıdır:

def matrix_multiply(X, Y):
    n = len(X)
    result = [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += X[i][k] * Y[k][j]

    return result

Bu kod parçacığı, iki nxn matrisi çarpar. Üç iç içe döngü nedeniyle, bu işlem O(n^3) karmaşıklığına sahiptir.

 

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...