Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Matematiksel kümeler üzerinde Birleşim (Union), Kesişim (Intersection), Birleştirme (MERGE) ve Bölme (SPLIT) işlemlerini kapsayan veri yapıları şemasıdır.
Küme İşlemleri, bilgisayar bilimlerinde soyut veri türü olarak kümelerin (set) verimli şekilde saklanmasını ve bu kümeler üzerindeki ilişkilerin hesaplanmasını sağlar. Aho kaynağında bu yapılar detaylı olarak incelenmiştir.
MFSET (Merge-Find Set), aralarında eşdeğerlik ilişkisi (equivalence relation) olan eleman gruplarını dinamik olarak birleştiren ve sorgulayan yapıyı tanımlar. Union-Find veri yapısı bu ADT'nin en yaygın gerçekleşmesidir.
MERGE ve SPLIT set algoritmaları, sıralı kümeler üzerinde çalışır. MERGE, iki sıralı kümeyi birleştirip tek bir sıralı küme yaparken; SPLIT, bir kümeyi belirtilen bir sınır değerine göre o değerden küçükler ve büyükler olarak iki ayrı kümeye böler. Set Union ve Intersection ise sırasıyla küme birleşimi ve kesişimi işlemlerini gerçekleştirir.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function setUnion(setA: Set, setB: Set): Set { 2 const result = new Set(setA); 3 for (const item of setB) {4 result.add(item);5 }6 return result;7}89function setIntersection(setA: Set, setB: Set): Set { 10 const result = new Set(); 11 for (const item of setA) {12 if (setB.has(item)) {13 result.add(item);14 }15 }16 return result;17}1819function setSplit(setS: Set, pivot: number): [Set, Set] { 20 const set1 = new Set(); 21 const set2 = new Set(); 22 for (const val of setS) {23 if (val < pivot) {24 set1.add(val);25 } else if (val > pivot) {26 set2.add(val);27 }28 }29 return [set1, set2];30}İki kümeyi virgülle ayırarak girin (Kümeleri ; ile ayırın). Örnek: 1, 2, 3; 3, 4, 5
İki kümeyi virgülle ayırarak girin (Kümeleri ; ile ayırın). Örnek: 1, 2, 3; 3, 4, 5
En İyi Durum: O(n + m)
Ortalama Durum: O(n + m)
En Kötü Durum: O(n + m)
O(n + m) sonuç kümesi için - Bu algoritmanın karmaşıklığı belirtilmemiş.
Küme İşlemleri ve MFSET (Set Operations & MFSET) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: