- Katılım
- 11 Mart 2016
- Mesajlar
- 991
- Elmaslar
- 911
- Puanlar
- 19.300
- Yaş
- 22
- Yer
- Aydın / Kuşadası
- Minecraft
- SYN_T3SL4
08.02.2021 tarihinde "Algoritma Karmaşıklığı" konulu bir yazı paylaştım. Bu yazıda her ne kadar algoritma karmaşıklığından ve genel hatlarıyla algoritmalardan bahsetsemde arka planda birçok konuya daha değinilmesi gerekiyor. Bunlardan en önemlileri arama algoritmaları.
Düşünsenize bir claim eklentisi yapacaksınız ve bunun için birden fazla kontrolle sonuca ulaşmanız gerekiyor. Sunucuyu yormadan en kısa yolu nasıl seçeceksiniz. Kendi eklentim olan T3SL4Claim'den alıntılar yaparak bir sorunu çözüme kavuşturmayı düşünüyorum. Bu sayede en basit arama algoritmasından daha da üst seviyelere çıkabiliriz.
Öncelikle bir algoritmanın / bir fonksiyonun karmaşıklığının hesaplanmasına değinmek istiyorum.
Hesaplamaları yaparken değerlendirme kriteri satırların adi satır olup olmadığıdır.
Örneğin:
int claimHoloSlot;
bu satır bir adi satırdır ve karmaşıklığa etkisi 1'dir.
for(int i=0; i<claimHoloSlot; i++) {
}
Bu satırın karmaşıklığa katkısı n'dir. Burada n döngünün uzunluğunu ifade eder.
for(int i=0; i<claimHoloSlot; i++) {
for(int j=0; j<claimHoloSlot+2; j++) {
}
}
Bu satırın karmaşıklığa katkısı ise n^2'dir (n kare). Sebebi ise çift döngü olmasıdır. Yani içteki döngü dıştaki kadar dönecek bu n dir bir de içteki döngünün kendi değeri olan n var buradan da n^2 elde edilir.
Bu konuda değerlendireceğim sıralama algoritmalarına değinirsek:
- Linear search,
- Binary search.
Linear Search:
Çoğunlukla kullanılan arama algoritması linear search'tür. Bunun sebebi hem her duruma rahat bir şekilde uyarlanabilmesi hem de yapısı itibariyle basit olmasıdır.
Şimdi karşımızda 10 kişi olsun ve bu 10 kişiden sadece 1'i mavi gözlü olsun. Yazacağınız programın amacı ise bu 1 mavi gözlüyü bulmak olsun. O zaman ne yaparsınız 0'dan başlar 9'a kadar gidersiniz ta ki mavi gözlüyü bulana kadar. Mavi gözlü 0. kişi de çıkabilir 9. kişi de bu tamamen girilen veriye bağlıdır. İşte bu tarz bir arama linear yani doğrusal aramadır. Ve doğrusal arama bazen worst case (Big-O) bazen de Theta notasyonunu verebilir.
Binary Search:
Binary search algoritması için öncelikle girilen verileri sıralamanız gerekmektedir. Sıralama algoritmalarına daha sonra değineceğim için şimdilik sıralanmış olarak varsayabiliriz. Sıralı bir liste üzerinde arama yaparken algoritmanız her aramada listenizi parçalayacaktır bu da karmaşıklığa pozitif olarak etki edecek. Binary search algoritmasının karmaşıklığı (log n)'dir.
Girilen verinin uzunluğu (n) = 100 olsun
Linear search big-O'su = O(n)'den 100'dür.
Binary Search big-O'su = O(log n)'den log100 'dür buradan da 2 bulunur.
Aradaki zaman farkı hafife alınmayacak kadar fazladır.
Şimdiden bol kodlamalar dilerim :))
Düşünsenize bir claim eklentisi yapacaksınız ve bunun için birden fazla kontrolle sonuca ulaşmanız gerekiyor. Sunucuyu yormadan en kısa yolu nasıl seçeceksiniz. Kendi eklentim olan T3SL4Claim'den alıntılar yaparak bir sorunu çözüme kavuşturmayı düşünüyorum. Bu sayede en basit arama algoritmasından daha da üst seviyelere çıkabiliriz.
Öncelikle bir algoritmanın / bir fonksiyonun karmaşıklığının hesaplanmasına değinmek istiyorum.
Hesaplamaları yaparken değerlendirme kriteri satırların adi satır olup olmadığıdır.
Örneğin:
int claimHoloSlot;
bu satır bir adi satırdır ve karmaşıklığa etkisi 1'dir.
for(int i=0; i<claimHoloSlot; i++) {
}
Bu satırın karmaşıklığa katkısı n'dir. Burada n döngünün uzunluğunu ifade eder.
for(int i=0; i<claimHoloSlot; i++) {
for(int j=0; j<claimHoloSlot+2; j++) {
}
}
Bu satırın karmaşıklığa katkısı ise n^2'dir (n kare). Sebebi ise çift döngü olmasıdır. Yani içteki döngü dıştaki kadar dönecek bu n dir bir de içteki döngünün kendi değeri olan n var buradan da n^2 elde edilir.
Bu konuda değerlendireceğim sıralama algoritmalarına değinirsek:
- Linear search,
- Binary search.
Linear Search:
Çoğunlukla kullanılan arama algoritması linear search'tür. Bunun sebebi hem her duruma rahat bir şekilde uyarlanabilmesi hem de yapısı itibariyle basit olmasıdır.
Şimdi karşımızda 10 kişi olsun ve bu 10 kişiden sadece 1'i mavi gözlü olsun. Yazacağınız programın amacı ise bu 1 mavi gözlüyü bulmak olsun. O zaman ne yaparsınız 0'dan başlar 9'a kadar gidersiniz ta ki mavi gözlüyü bulana kadar. Mavi gözlü 0. kişi de çıkabilir 9. kişi de bu tamamen girilen veriye bağlıdır. İşte bu tarz bir arama linear yani doğrusal aramadır. Ve doğrusal arama bazen worst case (Big-O) bazen de Theta notasyonunu verebilir.
Binary Search:
Binary search algoritması için öncelikle girilen verileri sıralamanız gerekmektedir. Sıralama algoritmalarına daha sonra değineceğim için şimdilik sıralanmış olarak varsayabiliriz. Sıralı bir liste üzerinde arama yaparken algoritmanız her aramada listenizi parçalayacaktır bu da karmaşıklığa pozitif olarak etki edecek. Binary search algoritmasının karmaşıklığı (log n)'dir.
Girilen verinin uzunluğu (n) = 100 olsun
Linear search big-O'su = O(n)'den 100'dür.
Binary Search big-O'su = O(log n)'den log100 'dür buradan da 2 bulunur.
Aradaki zaman farkı hafife alınmayacak kadar fazladır.
Şimdiden bol kodlamalar dilerim :))
