Mobil Menü

Python ile Veri Yapıları ve Algoritmalar

1. Veri Yapıları ve Algoritmalara Giriş

Veri Yapısı (Data Structure), verilerin belirli bir düzen içinde saklanması ve gerektiğinde verimli bir şekilde erişilmesini sağlayan yöntemler bütünüdür. Veri yapılarının seçimi, bir programın performansını ve bellekte kapladığı yeri doğrudan etkiler.

Algoritma (Algorithm) ise bir problemi çözmek için izlenen adımlar dizisidir. Bu adımlar verilerin işlenmesini, sıralanmasını veya belirli işlemlerin yapılmasını içerir. İyi bir algoritma, doğru ve en verimli çözümü sunmalıdır.

Veri Yapılarının ve Algoritmaların Önemi

Veri yapıları ve algoritmalar, programların performansını optimize etmek, bellek yönetimini iyileştirmek ve hızlı çözümler geliştirmek için vazgeçilmezdir. Özellikle büyük veri setleri üzerinde çalışırken, yanlış yapı veya algoritma seçimi uygulamanın verimliliğini önemli ölçüde düşürebilir.

2. Temel Veri Yapıları

Veri yapılarını genel olarak doğrusal ve doğrusal olmayan veri yapıları olarak iki gruba ayırabiliriz:

2.1 Doğrusal Veri Yapıları

Doğrusal veri yapıları, verilerin belirli bir sırayla saklandığı yapılardır. Bu tür veri yapıları genellikle bir dizilim halinde çalışır ve veriler arasında ardışık bir ilişki bulunur.

1. Diziler (Arrays)
Diziler, aynı türden elemanların sıralı bir şekilde saklandığı veri yapılarıdır. Her bir elemana dizin (index) aracılığıyla erişilebilir. Dizilerin avantajları arasında hızlı veri erişimi ve sabit boyutlu olmaları bulunur. Ancak, boyutları sabit olduğundan dinamik veri ekleme veya çıkarma işlemlerinde esnek değildirler.

Örnek:

# Python'da bir dizi tanımlama ve elemanlarına erişim
dizi = [10, 20, 30, 40, 50]
print(dizi[0])  # 10
print(dizi[3])  # 40

2. Bağlı Listeler (Linked Lists)
Bağlı listeler, birbirine düğümler (node) aracılığıyla bağlanan veri elemanlarından oluşur. Dizilerden farklı olarak, boyutları sabit değildir, yani dinamik veri ekleme ve çıkarma işlemleri oldukça verimlidir. Ancak, belirli bir elemana erişim zaman alabilir.

Örnek:

# Python'da basit bir bağlı liste düğüm tanımı
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Bağlı listeye eleman ekleme
ilk_düğüm = Node(10)
ikinci_düğüm = Node(20)
ilk_düğüm.next = ikinci_düğüm
print(ilk_düğüm.data)  # 10
print(ilk_düğüm.next.data)  # 20

3. Yığınlar (Stacks)
Yığınlar, LIFO (Last In, First Out – Son Giren İlk Çıkar) prensibine göre çalışan veri yapılarıdır. Veri ekleme ve çıkarma işlemleri sadece bir uçtan yapılır. Yığınlar, özellikle geri alma (undo) gibi işlemler için kullanılır.

Örnek:

# Python ile yığın işlemleri
yığın = []
yığın.append(10)  # Veri ekleme
yığın.append(20)
print(yığın.pop())  # 20 (Son eklenen çıkar)
print(yığın.pop())  # 10

4. Kuyruklar (Queues)
Kuyruklar, FIFO (First In, First Out – İlk Giren İlk Çıkar) prensibi ile çalışan veri yapılarıdır. İlk eklenen eleman ilk çıkar. Kuyruklar, görev sıralama gibi işlemler için sıkça kullanılır.

Örnek:

# Python'da kuyruk kullanımı
from collections import deque
kuyruk = deque()
kuyruk.append(10)  # Veri ekleme
kuyruk.append(20)
print(kuyruk.popleft())  # 10 (İlk eklenen çıkar)
print(kuyruk.popleft())  # 20

2.2 Doğrusal Olmayan Veri Yapıları

Doğrusal olmayan veri yapıları, verilerin karmaşık bir biçimde bağlandığı ve genellikle dallanma yapılarının kullanıldığı yapılardır.

1. Ağaçlar (Trees)
Ağaçlar, düğümlerden oluşan hiyerarşik veri yapılarıdır. Ağaç yapısında bir kök (root) düğümü bulunur ve bu düğümden dallanarak diğer düğümler oluşturulur. Her düğümün çocuk (child) ve ebeveyn (parent) düğümleri olabilir. En yaygın ağaç türü ikili ağaçlardır (Binary Tree).

Örnek:

# Python'da basit bir ikili ağaç düğümü tanımı
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# İkili ağaçta düğüm oluşturma
kök = TreeNode(10)
kök.left = TreeNode(5)
kök.right = TreeNode(15)
print(kök.data)  # 10
print(kök.left.data)  # 5
print(kök.right.data)  # 15

2. Grafikler (Graphs)
Grafikler, düğümler (veya köşeler – vertices) ve bu düğümleri birbirine bağlayan kenarlardan (edges) oluşur. Grafikler yönlü veya yönsüz olabilir. Özellikle yol bulma, sosyal ağ analizi gibi alanlarda kullanılırlar.

Örnek:

# Python'da basit bir grafik tanımı
grafik = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}
print(grafik["A"])  # ["B", "C"]

3. Temel Algoritmalar

Algoritmalar, veri yapıları üzerinde yapılan işlemlerde kullanılır. Bu bölümde, sıralama ve arama gibi temel algoritmalara değineceğiz.

3.1 Sıralama Algoritmaları

Sıralama algoritmaları, veri setlerini belirli bir sıraya göre düzenler. En bilinen sıralama algoritmaları şunlardır:

1. Bubble Sort (Kabarcık Sıralama)
Diziyi tekrar tekrar dolaşarak yan yana olan iki elemanı karşılaştırır ve yanlış sırada olanları yer değiştirir. Bu işlem, tüm elemanlar doğru sırada olana kadar devam eder.

Örnek:

# Python'da Bubble Sort algoritması
def bubble_sort(dizi):
    n = len(dizi)
    for i in range(n):
        for j in range(0, n - i - 1):
            if dizi[j] > dizi[j + 1]:
                dizi[j], dizi[j + 1] = dizi[j + 1], dizi[j]
    return dizi

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

2. Selection Sort (Seçme Sıralaması)
Her adımda dizinin en küçük elemanını bulur ve bu elemanı sırasıyla dizinin başına taşır. Bu işlem dizi tamamen sıralanana kadar devam eder.

Örnek:

# Python'da Selection Sort algoritması
def selection_sort(dizi):
    for i in range(len(dizi)):
        min_idx = i
        for j in range(i + 1, len(dizi)):
            if dizi[min_idx] > dizi[j]:
                min_idx = j
        dizi[i], dizi[min_idx] = dizi[min_idx], dizi[i]
    return dizi

print(selection_sort([64, 25, 12, 22, 11]))

3.2 Arama Algoritmaları

Arama algoritmaları, belirli bir veri kümesi içinde bir değeri bulmaya yönelik algoritmalardır. En yaygın arama algoritmaları, Doğrusal Arama (Linear Search) ve İkili Arama (Binary Search)‘tır.

1. Doğrusal Arama (Linear Search)

Doğrusal arama, aranan değeri bulana kadar verileri sırayla tarar. Basit yapısı nedeniyle kolayca anlaşılabilir, ancak büyük veri kümelerinde verimli değildir.

Örnek:

# Python'da Doğrusal Arama algoritması
def linear_search(dizi, aranacak_deger):
    for i in range(len(dizi)):
        if dizi[i] == aranacak_deger:
            return i  # Değer bulunduysa indeksi döndür
    return -1  # Değer bulunamadıysa -1 döndür

print(linear_search([10, 20, 30, 40, 50], 30))  # Çıktı: 2
print(linear_search([10, 20, 30, 40, 50], 60))  # Çıktı: -1

2. İkili Arama (Binary Search)

İkili arama, sıralı bir dizi içinde çalışan, oldukça hızlı bir arama algoritmasıdır. Bu algoritma, diziyi sürekli ikiye bölerek aranan değeri arar. Bu nedenle, ikili aramanın çalışabilmesi için dizinin önceden sıralanmış olması gerekir.

Örnek:

# Python'da İkili Arama algoritması
def binary_search(dizi, aranacak_deger):
    sol, sag = 0, len(dizi) - 1
    while sol <= sag:
        orta = (sol + sag) // 2
        if dizi[orta] == aranacak_deger:
            return orta
        elif dizi[orta] < aranacak_deger:
            sol = orta + 1
        else:
            sag = orta - 1
    return -1

print(binary_search([10, 20, 30, 40, 50], 30))  # Çıktı: 2
print(binary_search([10, 20, 30, 40, 50], 60))  # Çıktı: -1

Karmaşıklık Analizi

  • Doğrusal Arama: O(n) – En kötü durumda tüm elemanları taraması gerekebilir.
  • İkili Arama: O(log n) – Her adımda arama alanını ikiye böldüğü için oldukça verimlidir.

4. Gelişmiş Veri Yapıları

Daha karmaşık veri yapıları, özellikle büyük veri kümeleri ve verimli arama, sıralama gibi işlemler için gereklidir. Bu bölümde ağaçlar ve hash tablolar gibi daha ileri düzey veri yapılarından bahsedeceğiz.

4.1 İkili Arama Ağaçları (Binary Search Trees – BST)

İkili arama ağaçları, her düğümün sol çocuğunun değerinin küçük, sağ çocuğunun değerinin büyük olduğu bir ağaç yapısıdır. BST’ler, veriyi sıralı bir şekilde saklamak ve hızlı arama işlemleri yapmak için kullanılır.

Özellikler:

  1. Sol alt ağaçtaki her düğümün değeri, ebeveyn düğümden küçüktür.
  2. Sağ alt ağaçtaki her düğümün değeri, ebeveyn düğümden büyüktür.

Örnek:

# Python'da basit bir İkili Arama Ağacı tanımı
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = TreeNode(data)
        else:
            self._insert_recursive(self.root, data)

    def _insert_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = TreeNode(data)
            else:
                self._insert_recursive(node.left, data)
        else:
            if node.right is None:
                node.right = TreeNode(data)
            else:
                self._insert_recursive(node.right, data)

# İkili arama ağacı oluşturma ve eleman ekleme
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(2)
bst.insert(7)

4.2 AVL Ağaçları

AVL ağaçları, dengeli bir ikili arama ağacıdır. Her düğüm için sol ve sağ alt ağaçların yüksekliği en fazla bir farkla değişebilir. Bu denge durumu, ağaç işlemlerinin zaman karmaşıklığını O(log n) düzeyinde tutar. AVL ağaçları, her ekleme veya silme işleminden sonra ağaç dengelenerek hızlı erişimi korur.

Özellikler:

  • Her düğümün yükseklik farkı en fazla bir olmalıdır.
  • Dengeleme işlemi için rotasyonlar kullanılır: sağa, sola, sağ-sol ve sol-sağ rotasyonları.

4.3 Hash Tablolar

Hash tablolar, anahtar-değer çiftlerini depolamak için kullanılan verimli veri yapılarıdır. Hash fonksiyonu, anahtarları belirli bir indeksle ilişkilendirir ve böylece veri, bellekte belirli bir yerde saklanır. Bu sayede arama ve ekleme işlemleri genellikle O(1) karmaşıklığa sahiptir.

Örnek:

# Python'da basit bir hash tablosu kullanımı (dictionary)
hash_tablosu = {}
hash_tablosu["elma"] = "Apple"
hash_tablosu["muz"] = "Banana"
print(hash_tablosu["elma"])  # Çıktı: Apple

Karmaşıklık Analizi

  • İkili Arama Ağacı (BST): Ortalama O(log n), en kötü durumda O(n).
  • AVL Ağacı: O(log n) – Dengeleme işlemleri sayesinde her zaman dengeli kalır.
  • Hash Tablo: Ortalama O(1), en kötü durumda O(n).

5. Gelişmiş Algoritmalar

Bu bölümde, daha karmaşık problemlere yönelik algoritmalara değineceğiz. Özellikle grafik algoritmaları, dinamik programlama ve sıralama algoritmalarında farklı yöntemlere yer vereceğiz.

5.1 Dinamik Programlama (Dynamic Programming)

Dinamik programlama, büyük problemleri daha küçük ve tekrarlayan alt problemlere bölerek çözmeye yönelik bir yöntemdir. Alt problemler çözülüp kaydedilir, böylece aynı alt problem tekrar ortaya çıktığında yeniden hesaplanması gerekmez. Bu teknik, genellikle rekürsiyon ile birlikte kullanılır.

Örnek: Fibonacci Sayıları: Fibonacci serisini dinamik programlama ile hesaplamak.

# Python'da dinamik programlama ile Fibonacci hesaplama
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))  # Çıktı: 55

5.2 Grafik Algoritmaları

Grafik algoritmaları, düğüm ve kenar yapılarında çeşitli işlemler yapmak için kullanılır. Örneğin, en kısa yol bulma algoritmaları ve dolaşma (traversal) algoritmaları grafikler üzerinde çalışır.

1. Derinlik Öncelikli Arama (Depth-First Search – DFS)
Derinlik öncelikli arama, grafikte bir düğümden başlayarak mümkün olduğunca derine iner. DFS, grafik üzerinde belirli bir yolu veya bileşeni bulmak için idealdir.

Örnek:

# Python'da grafik üzerinde DFS
def dfs(grafik, düğüm, ziyaret_edildi=None, sonuç=None):
    if ziyaret_edildi is None:
        ziyaret_edildi = set()
    if sonuç is None:
        sonuç = []
    
    if düğüm not in ziyaret_edildi:
        print(düğüm)  # Ziyaret edilen düğümü yazdır
        sonuç.append(düğüm)  # Ziyaret edilen düğümü sonuca ekle
        ziyaret_edildi.add(düğüm)
        for komsu in grafik[düğüm]:
            dfs(grafik, komsu, ziyaret_edildi, sonuç)
    
    return sonuç  # Ziyaret edilen düğümlerin listesini döndür

# Grafik tanımı
grafik = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

sonuç = dfs(grafik, 'A')
print("Ziyaret edilen düğümler:", sonuç)

5.3 Genişlik Öncelikli Arama (Breadth-First Search – BFS)

Genişlik Öncelikli Arama (BFS), grafikte bir düğümden başlayarak önce aynı seviyedeki düğümleri dolaşır. BFS, özellikle kısa yol bulma gibi işlemler için kullanışlıdır. Bir kuyruk veri yapısı kullanılarak, her düğüm seviyesine göre sırayla ziyaret edilir.

Örnek:

# Python'da grafik üzerinde BFS
from collections import deque

def bfs(grafik, başlangıç):
    ziyaret_edildi = set()
    kuyruk = deque([başlangıç])
    ziyaret_edildi.add(başlangıç)

    while kuyruk:
        düğüm = kuyruk.popleft()
        print(düğüm)
        for komsu in grafik[düğüm]:
            if komsu not in ziyaret_edildi:
                kuyruk.append(komsu)
                ziyaret_edildi.add(komsu)

# Grafik tanımı
grafik = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(grafik, 'A')

Bu kod, ‘A’ düğümünden başlayarak tüm düğümleri genişlik öncelikli bir sırayla dolaşır.

BFS ve DFS Karşılaştırması

  • BFS: Genellikle kısa yol bulma işlemlerinde kullanılır, çünkü düğümleri katman katman dolaşır.
  • DFS: Derinlere inerek dolaşır ve özellikle dolaşılamayan bölgeleri bulmak için uygundur.

5.4 Dijkstra’nın En Kısa Yol Algoritması

Dijkstra’nın algoritması, bir grafikte belirli bir düğümden diğer düğümlere olan en kısa yolları bulmak için kullanılır. Bu algoritma, her düğüm için minimum maliyetli yolu bulmak amacıyla bir öncelik kuyruğu kullanır.

Örnek:

# Python'da Dijkstra'nın algoritması
import heapq

def dijkstra(grafik, başlangıç):
    mesafe = {düğüm: float('inf') for düğüm in grafik}
    mesafe[başlangıç] = 0
    öncelik_kuyruğu = [(0, başlangıç)]

    while öncelik_kuyruğu:
        mevcut_mesafe, düğüm = heapq.heappop(öncelik_kuyruğu)

        if mevcut_mesafe > mesafe[düğüm]:
            continue

        for komsu, maliyet in grafik[düğüm].items():
            mesafe_yeni = mevcut_mesafe + maliyet

            if mesafe_yeni < mesafe[komsu]:
                mesafe[komsu] = mesafe_yeni
                heapq.heappush(öncelik_kuyruğu, (mesafe_yeni, komsu))

    return mesafe

# Grafik tanımı (ağırlıklı)
grafik = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(grafik, 'A'))

Bu algoritma, ‘A’ düğümünden diğer düğümlere olan en kısa yolları hesaplar.

Karmaşıklık Analizi

  • Dijkstra’nın algoritması: O((V + E) log V), burada V düğüm sayısı ve E kenar sayısıdır.

6. Karmaşıklık Analizi ve Big-O Notasyonu

Big-O Notasyonu, algoritmaların zaman veya alan karmaşıklığını ifade etmek için kullanılan bir yöntemdir. Bir algoritmanın performansını anlamak ve hangi durumlarda daha verimli olduğunu analiz etmek için bu notasyon kullanılır.

Zaman Karmaşıklığı (Time Complexity)

Zaman karmaşıklığı, bir algoritmanın çalışma süresinin, girdi boyutuna göre nasıl değiştiğini ifade eder. Örnek olarak farklı zaman karmaşıklıklarını inceleyelim:

  • O(1): Sabit zamanlı, veri boyutu ne olursa olsun süresi değişmez. Örneğin, bir dizinin belirli bir indeksine erişim.
  • O(log n): Logaritmik zamanlı, genellikle böl ve fethet stratejileri (ikili arama gibi) kullanılır.
  • O(n): Doğrusal zamanlı, algoritma girdinin her bir elemanını işlemek zorundadır.
  • O(n log n): Genellikle sıralama algoritmalarında görülür.
  • O(n^2): Kare zamanlı, iç içe döngüler gibi durumlarda ortaya çıkar (örneğin, kabarcık sıralama).

Örnek Big-O notasyonları:

# O(1) örneği
def sabit_zaman(dizi):
    return dizi[0]  # Sabit zamanda erişim

# O(n) örneği
def doğrusal_zaman(dizi):
    toplam = 0
    for eleman in dizi:
        toplam += eleman
    return toplam

# O(n^2) örneği
def kare_zaman(dizi):
    for i in range(len(dizi)):
        for j in range(len(dizi)):
            print(dizi[i], dizi[j])

Alan Karmaşıklığı (Space Complexity)

Alan karmaşıklığı, algoritmanın çalışırken kullandığı ek bellek miktarını ifade eder. Özellikle büyük veri işleyen algoritmaların bellek kullanımı önemlidir.

7. Karmaşık Problemler İçin Algoritma Tasarımı

Karmaşık problemleri çözmek için farklı algoritma tasarım teknikleri geliştirilmiştir. Aşağıda, yaygın kullanılan bazı teknikleri ve bu tekniklerle çözülebilecek problem örneklerini inceleyelim.

7.1 Böl ve Fethet (Divide and Conquer)

Bu teknik, problemi daha küçük alt problemlere bölerek her birini ayrı ayrı çözer ve ardından sonuçları birleştirir. Örneğin, Birleştirme Sıralaması (Merge Sort) bu tekniği kullanır.

Örnek:

# Python'da Birleştirme Sıralaması algoritması
def merge_sort(dizi):
    if len(dizi) > 1:
        orta = len(dizi) // 2
        sol_yarı = dizi[:orta]
        sağ_yarı = dizi[orta:]

        merge_sort(sol_yarı)
        merge_sort(sağ_yarı)

        i = j = k = 0
        while i < len(sol_yarı) and j < len(sağ_yarı):
            if sol_yarı[i] < sağ_yarı[j]:
                dizi[k] = sol_yarı[i]
                i += 1
            else:
                dizi[k] = sağ_yarı[j]
                j += 1
            k += 1

        while i < len(sol_yarı):
            dizi[k] = sol_yarı[i]
            i += 1
            k += 1

        while j < len(sağ_yarı):
            dizi[k] = sağ_yarı[j]
            j += 1
            k += 1

# Test
dizi = [12, 11, 13, 5, 6, 7]
merge_sort(dizi)
print(dizi)  # Çıktı: [5, 6, 7, 11, 12, 13]

7.2 Geri İzleme (Backtracking)

Geri izleme, bir çözümü deneme-yanılma yöntemiyle bulmaya çalışır. Her bir olası çözümü deneyerek doğru çözümü bulmaya çalışır, ancak başarısız olursa bir önceki adıma geri döner. Sudoku çözme veya 8 Kraliçe Problemi gibi problemler bu teknikle çözülür.

Örnek:

# Python'da basit geri izleme (8 Kraliçe Problemi)
def güvenli_mi(tahta, satır, sütun):
    for i in range(satır):
        if tahta[i] == sütun or \
           tahta[i] - i == sütun - satır or \
           tahta[i] + i == sütun + satır:
            return False
    return True

def kraliçe_kur(tahta, satır):
    if satır == len(tahta):
        print(tahta)  # Tahtayı yazdır
        return
    for sütun in range(len(tahta)):
        if güvenli_mi(tahta, satır, sütun):
            tahta[satır] = sütun  # Kraliçeyi yerleştir
            kraliçe_kur(tahta, satır + 1)  # Bir sonraki satıra geç

# 8 Kraliçe Problemi
def sekiz_kraliçe():
    tahta = [-1] * 8  # 8x8 tahtayı temsil eden bir liste
    kraliçe_kur(tahta, 0)

# Çözümü başlat
sekiz_kraliçe()

7.3 Dinamik Programlama (Dynamic Programming)

Dinamik programlama, büyük bir problemi alt problemlere bölerek çözmeye çalışır; ancak her alt problem yalnızca bir kez çözülür ve daha sonra sonuçları saklanır. Bu teknik, özellikle alt problemlerin tekrarlandığı durumlarda verimlidir. Dinamik programlamanın memoization (önbellekleme) ve tabulation (tablolama) olmak üzere iki temel yöntemi vardır.

Örnek: Knapsack Problemi Knapsack Problemi, belirli bir ağırlık kapasitesine sahip bir çantaya maksimum değeri sağlayacak şekilde nesneler seçmeyi amaçlar. Her nesnenin bir ağırlığı ve bir değeri vardır.

# Python'da dinamik programlama ile Knapsack Problemi çözümü
def knapsack(kapasite, ağırlıklar, değerler, n):
    K = [[0 for x in range(kapasite + 1)] for x in range(n + 1)]

    for i in range(n + 1):
        for w in range(kapasite + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif ağırlıklar[i-1] <= w:
                K[i][w] = max(değerler[i-1] + K[i-1][w-ağırlıklar[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

    return K[n][kapasite]

# Test
değerler = [60, 100, 120]
ağırlıklar = [10, 20, 30]
kapasite = 50
n = len(değerler)
print(knapsack(kapasite, ağırlıklar, değerler, n))  # Çıktı: 220

Bu örnekte, K tablosu, her alt problemi yalnızca bir kez çözer ve sonuçları saklayarak yeniden kullanır.

7.4 Açgözlü Algoritmalar (Greedy Algorithms)

Açgözlü algoritmalar, her adımda o an için en iyi görünen seçeneği seçerek çalışır. Çoğu zaman optimal çözümler sunmasa da bazı problemler için hızlı ve etkili sonuçlar verir.

Örnek: Para Bozdurma (Coin Change) En az sayıda bozuk para ile belirli bir miktarı bulmak için açgözlü algoritma kullanılır.

# Python'da açgözlü algoritma ile Para Bozdurma
def min_coin_change(paralar, miktar):
    paralar.sort(reverse=True)
    sonuç = []
    for para in paralar:
        while miktar >= para:
            miktar -= para
            sonuç.append(para)
    return sonuç

# Test
paralar = [1, 5, 10, 25]
miktar = 63
print(min_coin_change(paralar, miktar))  # Çıktı: [25, 25, 10, 1, 1, 1]

Bu örnekte, mümkün olan en büyük paradan başlayarak miktarı tamamlayan bir dizi bozuk para elde edilir.

8. Karmaşık Algoritmalar ve İleri Düzey Veri Yapıları

Bazı daha karmaşık veri yapıları ve algoritmalar, belirli problemler için daha verimli çözümler sunar. Örneğin:

8.1 Yığın (Heap)

Yığın, genellikle öncelik kuyruğu olarak kullanılan bir veri yapısıdır. Bir min heap‘te, her düğümün değeri çocuklarının değerinden küçüktür; bir max heap‘te ise tam tersi geçerlidir. Yığın yapısı Dijkstra gibi algoritmalarda önemli bir rol oynar.

Örnek:

import heapq

# Min-Heap örneği
sayılar = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(sayılar)
print(heapq.heappop(sayılar))  # En küçük eleman: 1
print(sayılar)  # Yığın içeriği

8.2 Graf Algoritmaları: Minimum Gerişim Ağaçları (Minimum Spanning Tree)

Graf teorisinde, Minimum Gerişim Ağacı (MST), bir grafın tüm düğümlerini kapsayan en düşük ağırlıklı ağaçtır. MST için en çok kullanılan algoritmalar Prim ve Kruskal‘dır.

Örnek: Kruskal Algoritması

class Kenar:
    def __init__(self, kaynak, hedef, ağırlık):
        self.kaynak = kaynak
        self.hedef = hedef
        self.ağırlık = ağırlık

# Birleştirme (Union-Find) yapısı
class Birleştir:
    def __init__(self, n):
        self.ebeveyn = list(range(n))
    
    def bul(self, i):
        if self.ebeveyn[i] != i:
            self.ebeveyn[i] = self.bul(self.ebeveyn[i])
        return self.ebeveyn[i]

    def birleştir(self, x, y):
        kök_x = self.bul(x)
        kök_y = self.bul(y)
        if kök_x != kök_y:
            self.ebeveyn[kök_x] = kök_y

def kruskal(graf, n):
    birleştir = Birleştir(n)
    mst = []
    graf = sorted(graf, key=lambda kenar: kenar.ağırlık)

    for kenar in graf:
        if birleştir.bul(kenar.kaynak) != birleştir.bul(kenar.hedef):
            birleştir.birleştir(kenar.kaynak, kenar.hedef)
            mst.append(kenar)
    
    return mst

# Test grafı
graf = [
    Kenar(0, 1, 10), Kenar(0, 2, 6),
    Kenar(0, 3, 5), Kenar(1, 3, 15),
    Kenar(2, 3, 4)
]
mst = kruskal(graf, 4)
for kenar in mst:
    print(f"Kaynak: {kenar.kaynak}, Hedef: {kenar.hedef}, Ağırlık: {kenar.ağırlık}")

Sonuç

Bu kapsamlı rehberde, veri yapıları ve algoritmaların temellerinden başlayarak sıralama, arama, ağaç yapıları, graf teorisi ve daha ileri düzeyde karmaşık algoritmalara kadar geniş bir yelpazede bilgi sunduk. Algoritma ve veri yapısı seçimi, verinin türüne ve işlenen problemin özelliklerine göre yapılmalıdır. Özellikle karmaşıklık analizleri, bu seçimi doğru bir şekilde yapmamızda bize rehberlik eder.

Osman Bayrak
Osman Bayrak

Yazılım Mühendisiyim. Teknoloji ve yazılıma meraklıyım.

Articles: 199