Herkese merhaba bu yazıda yazacağımız kodların analizi çıkartarak daha az yer ve daha az işlem ile en optimum kod yazmaya kurallarına bakacağız.
Bilgisayar bilimlerinde algoritmaların çalışması için 2 temel kaynak vardır
1-Hafıza(RAM)
2-Zaman(Hız)
Bilgisayar programları temelde bu 2 unsur üzerinde çalışır yani program ne kadar az yer kaplıyorsa ve hızlıysa iyidir fakat fazla yer kaplıyor ve yavaş çalışırsa o kötü programdır ya da kötü yazılmıştır.
İşte bu yazıda kötü program ve iyi programın matematiksel anlamına bakacağız.
Bir algoritmanın zaman ve yer bakımından maliyetlerinin incelenmesine o algoritmanın karmaşıklığı denir. Bu karmaşıklığı temelde 3 türde ifade ederiz
- En iyi durum
- Ortalama durum
- En kötü durum
Bu 3 durumun incelenmesi oldukça uzun olduğundan içlerinden en önemli olan en kötü durum analizi inceleyeceğiz.
En kötü durum örneği: Sıralamak istediğimiz sayıların tamamının tersten sıraları olması
Algoritmalarımızı analiz ederken büyüme oranı denen tabiri kullanacağız bu şey matematik dersinde gördüğümüz limit teoremi ile ilişkili. Yani aslında burada söylemek istediğim algoritmanın çalışma süresinin sonsuza giderken hayal etmenizi istiyorum. Örneğin bir for döngüsünün sonsuza kadar çalıştığını düşünün.
int n = 100
for (int i = 1;i<n;i++){
printf(“Merhaba Dünya”);
}
Kodumuzda bir döngü ve onun içinde de ekrana yazma komutu var bunun sonucunu her halde tahmin edebiliyorsunuzdur.
Yukarıdaki kod parçacığının en kötü durumda karmaşıklığı O(n) Neden? Çünkü bu kod parçacığı sonsuza giderken n kere çalışacak
Bir örnek daha vererek daha iyi açıklayalım
int n = 100
for (int i = 1;i<n;i++){
printf(“Merhaba Dünya”);
}
int k = 100
for (int j= 1;i<k;j++){
printf(“Merhaba Dünya2”);
}
Yukarıda ki kodda alt alta 2 tane döngü yazdım bunun karmaşıklığını bulalım
Üsttekinin karmaşıklığı O(n)+ Alttakinin karmaşıklığı O(n) = O(2n)’dir
Ancak başta da söylediğim sonsuza gitme muhabbetinden dolayı denklemimizde ki sabit sayıları atarız ve geriye O(n) kalır.
Biraz hızlanalım …
int n = 100
int k = 100
for (int i = 1;i<n;i++){
for (int j= 1;i<k;j++){
printf(“Merhaba Dünya”);
}
}
Karmaşıklı : O(n)*O(n) =O(n^2)
buradaki 2’yi atmamamızın sebebi bir fonksiyon tanımından olduğundan
Devamm…
int n = 100
for (int i = 1;i*2<n;i++){
printf(“Merhaba Dünya”);
}
Yukarıdaki kod i’nin hep katlanarak 7 defa çalıştığında bitecek
Sırasıyla i’nin değerleri:1-2-4-6-8-16-32-64-128(DUR)
Karmaşıklığı:Log(n) neden logaritmik fonksiyon olduğunu merak edersiniz log 2 tabanında 100’ün sonucunda saklı
Yazıma son vermeden aşağıdaki fotoğraftan konuyu özetlemeye çalışayım. x kordinatı girdi sayısı yani döngünün ne kadar döneceğini söyler y kordinatı ise zamanı. Yani bizim O(log(n))’de çalışan bir algoritmamız elimizde ki veri ne kadar çok olursa olsun hep hızlı çalışır demek mesala bizim O(n^2)’de çalışan bir algoritmamız olduğunda ki duruma bakın facia! 100 veride bu farkı anlayamayabiliriz fakat 100 milyon veri olduğunda saatlerce bilgisayar karşında oturmaktan belimizi ağırdığında farkı anlarız. Sizde pratikte algoritmaların çalışma zamanlarını test etmek isterseniz aşağıdaki fotoğrafta ki sıralama algoritmalarını iyi olduğunuz bir dile de 1 milyon sayıyı tersten sıralayarak test edebilirsiniz.
Yukarıdaki tabloya birde Sayma Sıralama algoritmasını ekliyorum. Bu algoritma en kötü durumda O(n+k)’da çalışır neden n+k olduğunu biraz araştırıp bulabilirsiniz.
