📘 Asimptotik Notasyonlar - Ders Notu 🎯 O-Notasyonu (Big-O) - Üst Sınır Tanım: Algoritmanın en kötü durum performansını gösterir. f(n) = O(g(n)) ⟺ ∃c > 0, ∃n₀ ≥ 0 : ∀n ≥ n₀ → f(n) ≤ c·g(n) + b Basit açıklama: f(n) fonksiyonu, yeterince büyük n değerleri için c·g(n)‘den daha hızlı büyümez. 📝 Örnek Çözüm Soru: T(n) = 32n² + 17n + 32 için Big-O’yu bulun. Cevap: T(n) = O(n²) Açıklama: ...
📊 Rekürsif Analiz - Kısa Notlar 🔄 Yerine Koyma Metodu (Substitution) Ne Zaman Kullanılır? T(n) = T(n-1) + f(n) tipindeki rekürsiyonlar için Örnek: T(n) = T(n-1) + n Adımlar: T(n) = T(n-1) + n = T(n-2) + (n-1) + n = T(n-3) + (n-2) + (n-1) + n = ... = T(0) + [1 + 2 + 3 + ... + n] k adım sonra: T(n) = T(n-k) + [(n-k+1) + ... + n] Taban duruma ulaş: n-k = 0 → k = n ...
🔄 Sıralama Algoritmaları 📋 İçindekiler Bubble Sort Selection Sort Insertion Sort Merge Sort Quick Sort 🫧 Bubble Sort Çalışma Mantığı Yan yana elemanları karşılaştırarak büyük elemanları sona doğru “yüzdürür”. Her turda en büyük eleman yerine yerleşir. Adımlar Dizinin başından itibaren yan yana elemanları karşılaştır Soldaki sağdakinden büyükse yer değiştir Dizinin sonuna kadar devam et Her turda bir eleman daha yerine oturur Tüm dizi sıralanana kadar tekrarla Görsel Gösterim [5, 3, 8, 4, 2] → İlk durum [3, 5, 4, 2, 8] → 1. tur (8 yerine oturdu) [3, 4, 2, 5, 8] → 2. tur (5 yerine oturdu) [3, 2, 4, 5, 8] → 3. tur [2, 3, 4, 5, 8] → Sıralı ✓ Komplekslik Zaman: O(n²) - En kötü ve ortalama Zaman: O(n) - En iyi durum (zaten sıralıysa) Alan: O(1) - Yerinde sıralama Kullanım Alanları Küçük veri setleri Eğitim amaçlı Neredeyse sıralı diziler için 🎯 Selection Sort Çalışma Mantığı Her adımda dizinin geri kalanından en küçük elemanı bulup başa yerleştirir. ...
🔗 Linked List - Bağlı Listeler 📋 İçindekiler Giriş Temel Yapı Linked List Türleri Temel İşlemler Zaman Karmaşıklığı Avantaj ve Dezavantajlar Kod Örnekleri Kullanım Alanları 🎯 Giriş Linked List (Bağlı Liste), her elemanın kendinden sonraki elemana işaret ettiği, dinamik bir veri yapısıdır. Veriler bellekte ardışık olarak saklanmaz; her node (düğüm) bir sonrakinin adresini içerir. 💡 Temel Özellik: Boyut dinamik olarak değişir, sabit boyut sınırı yoktur! ...
📚 Stack (Yığın) Veri Yapısı 🎯 Stack Nedir? Stack (Yığın), Last-In-First-Out (LIFO) prensibiyle çalışan soyut bir veri yapısıdır. Yani son eklenen eleman, ilk çıkarılır. Günlük Hayattan Örnek Bir tabak yığınını düşünün: Yeni tabakları en üste koyarsınız Tabak alırken de en üsttekini alırsınız En alttaki tabağa ulaşmak için üstteki tüm tabakları kaldırmanız gerekir ┌───────┐ │ 3 │ ← En üst (Top) - İlk çıkarılacak ├───────┤ │ 2 │ ├───────┤ │ 1 │ ← En alt └───────┘ 🔧 Temel Operasyonlar 1️⃣ push(E e) - Ekleme Element yığının en üstüne eklenir. ...
🔍 Arama Algoritmaları 🎯 Temel Problem Arama nedir? Çok sayıda benzer nesne içinden belirli özelliklere sahip olanları tespit etme işlemidir. Günlük Hayattan Örnekler Problem Türü Pratik Kullanım 🔤 Pattern Matching Google’da kelime arama, metin editörlerinde “Bul” özelliği 📊 Veri Tabanı Sorgusu Öğrenci bilgi sisteminde öğrenci bulma, envanter kontrolü 🏗️ Temel Yapı Taşları Element Sınıfı Tasarımı class Element { int searchKey; // Anahtar alan (örn: 2019280045) String name; // İsim String surname; // Soyisim String department; // Bölüm } Veri Koleksiyonu Oluşturma final int MAXELEM = 1000; Element[] database = new Element[MAXELEM]; 📌 Hedef: database[i].searchKey == arananAnahtar şartını sağlayan elemanı bulmak ...
Hash Tabloları 📌 Neden Hash Tabloları? Binary Search’ün Özellikleri: Worst-case: O(log n) - çok verimli Gereksinimler: Sıralı veri + Doğrudan erişim Sıralı ekleme: O(n) - pratik olarak yavaş Hash Tabloları ile İyileştirme: Ekleme: Genelde O(1), worst-case O(n) Arama: Genelde O(1), worst-case O(n) 🔑 Hash Fonksiyonu Hash fonksiyonu, bir anahtarı (key) tablo indeksine dönüştürür. String için Örnek Hash Fonksiyonu public static int hash(String wort) { int m = 13; // Tablo boyutu (asal sayı olmalı) int k = 0; for (int i = 0; i < wort.length(); i++) { k += (int) wort.charAt(i); // ASCII/Unicode değerlerinin toplamı } return k % m; // Modulo ile indeks hesaplama } Hash Fonksiyonunun Özellikleri Uzay U (Sonsuz anahtar uzayı) ↓ Hash Fonksiyonu h(k) ↓ Hash Tablosu T [0...m-1] (Sonlu alan) Evrensel küme (U): Tüm olası anahtarlar Anahtar kümesi (S): Gerçekte kullanılan anahtarlar Hash tablosu (T): Sabit boyutlu m elemanlı dizi Önemli: Hash fonksiyonları genelde injektif değildir (farklı anahtarlar aynı indeksi verebilir) ⚠️ Önemli Not Tablo boyutu asal sayı olmalı! Bu, daha iyi dağılım sağlar. ...