Algoritma Analizi Nedir?
Algoritma analizini açıklamadan önce algoritmayı kısaca açıklayalım.
Algoritma nedir ?
Belli bir görevi yerine getiren sonlu sayıdaki işlevler diyebiliriz.
Algoritmaları sınıflandıracak olursak;
-Arama Algoritmaları
-Sıralama Algoritmaları
-Kök Bulma Algoritmaları
-Genetik Algoritmalar
-Kriptografik Algoritmalar
-Diğer Algoritmalar
Örnek bir sıralama(bubble sort) algoritması,
public void bubbleSort(int[] dizi)
{
for (int i = 0; i < dizi.Length - 1; i++)
{
for (int j = 1; j < dizi.Length - i; j++)
{
if (dizi[j] < dizi[j - 1])
{
int gecici = dizi[j - 1];
dizi[j - 1] = dizi[j];
dizi[j] = gecici;
}
}
}
}
Algoritma Analizi nedir?
Bilgisayar programlarının performans ve kaynak kullanımı üzerine yapılan çalışmalardır. Bilgisayar programlarında işin daha iyi nasıl gerçekleşebileceğini ele alır.
Algoritma analizinde öncelikle üzerinde durulan konu, algoritmanın performansıdır.
İşte tam bu noktada sorularımızı sorup cevabını bularak algoritma analizini açıklamaya çalışacağım.
Algoritma Analizi Temel Kavramlar
Yürütme zamanı ( Running Time)
Bir programın veya algoritmanın işlevini yerine getirebilmesi için, temel kabul edilen işlemlerden kaç adet çalıştırılması gerektiği bilgisidir.Bağımsız değişken elaman sayısıdır.
Örneğin n elemanlı bir küme için yürütme zamanı T(n) şeklinde gösterilir.
Zaman Karmaşıklığı ( Time Complexity)
Bir algoritmanın asimptotik notasyona göre karmaşıklık mertebesini gösteren ifadedir. Genellikle algoritmanın çok fazla eleman sayısı olması durumunda gerekli işlemlerin düzeyini gösterir.
Zaman karmaşıklığı, yürütme zamanı T(n) de olduğu gibi açık bir bağlantı olamayıp, asimptotik ifadelerle gösterilir.
Alan Maliyeti
Bir programın veya algoritmanın işlevini yerine getirmesi için gerekli bellek alanını veren bir bağıntı veya değerdir.Alan maliyeti program kodu,yığın ve veri için gerekli tüm alanları kapsar.
Program kodu için gerekli belek alanı veri için gerekli bellek alanının yanında ihmal edilecek düzeyde ise yalnızca veri alanı hesaplaması yeterlidir.
Ör: 4 bytelık tamsayı olan n elemanlı bir küme için alan maliyeti bağıntısı S(n)=4n şeklinde verilir
Alan Karmaşıklığı ( Space Complexity)
Alan karmaşıklığı eleman sayısı n’ nin çok büyük değerleri için bellek alanı gereksiniminin artış mertebesini gösteren asimptotik ifadelerdir. Bu amaçla zaman karmaşıklığında kullanılan asimptotik ifadelerle gösterilir.
Ör: Alan karnaşıklığı olarak 𝑶(𝒏 𝟐 ) verilirse bellek gereksiniminin n’nin büyük değerleri için en kötü durumda karesel arttığı ifade edilmektedir.
En İyi – Ortalama – En Kötü Durumlar (Best-Average-Worst Cases)
Yürütme zamanı, maliyet ve karmaşıklık hesaplanırken en iyi sonucun elde edildiği durum
en iyi durum (best case) dur.
En Kötü durum (worst case) ise en olumsuz koşulların gerçekleşmesi durumunda algoritmanın çözüm üretmesi için gerekli hesaplama sonucudur.
Big-O Notasyonu
Bir işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması diyebiliriz.Yada büyüme hızını gösterir de diyebiliriz.
Sık kullanılan büyüme hızları
Verilen iki algoritmanın çalışma zamanını T1(N) ve T2(N) fonksiyonları şeklinde gösterilir. Hangisinin daha iyi olduğunu belirlemek için bir yol belirlememiz gerekiyor.
– Big-O (Big O): Asimptotik üst sınır
– Big W (Big Omega): Asimptotik alt sınır
– Big Q (Big Teta): Asimptotik alt ve üst sınır
Big O Notasyonu
Algoritma nedir ?
Belli bir görevi yerine getiren sonlu sayıdaki işlevler diyebiliriz.
Algoritmaları sınıflandıracak olursak;
-Arama Algoritmaları
-Sıralama Algoritmaları
-Kök Bulma Algoritmaları
-Genetik Algoritmalar
-Kriptografik Algoritmalar
-Diğer Algoritmalar
Örnek bir sıralama(bubble sort) algoritması,
public void bubbleSort(int[] dizi)
{
for (int i = 0; i < dizi.Length - 1; i++)
{
for (int j = 1; j < dizi.Length - i; j++)
{
if (dizi[j] < dizi[j - 1])
{
int gecici = dizi[j - 1];
dizi[j - 1] = dizi[j];
dizi[j] = gecici;
}
}
}
}
Algoritma Analizi nedir?
Bilgisayar programlarının performans ve kaynak kullanımı üzerine yapılan çalışmalardır. Bilgisayar programlarında işin daha iyi nasıl gerçekleşebileceğini ele alır.
Algoritma analizinde öncelikle üzerinde durulan konu, algoritmanın performansıdır.
İşte tam bu noktada sorularımızı sorup cevabını bularak algoritma analizini açıklamaya çalışacağım.
Algoritma Analizi Temel Kavramlar
Yürütme zamanı ( Running Time)
Bir programın veya algoritmanın işlevini yerine getirebilmesi için, temel kabul edilen işlemlerden kaç adet çalıştırılması gerektiği bilgisidir.Bağımsız değişken elaman sayısıdır.
Örneğin n elemanlı bir küme için yürütme zamanı T(n) şeklinde gösterilir.
Zaman Karmaşıklığı ( Time Complexity)
Bir algoritmanın asimptotik notasyona göre karmaşıklık mertebesini gösteren ifadedir. Genellikle algoritmanın çok fazla eleman sayısı olması durumunda gerekli işlemlerin düzeyini gösterir.
Zaman karmaşıklığı, yürütme zamanı T(n) de olduğu gibi açık bir bağlantı olamayıp, asimptotik ifadelerle gösterilir.
Alan Maliyeti
Bir programın veya algoritmanın işlevini yerine getirmesi için gerekli bellek alanını veren bir bağıntı veya değerdir.Alan maliyeti program kodu,yığın ve veri için gerekli tüm alanları kapsar.
Program kodu için gerekli belek alanı veri için gerekli bellek alanının yanında ihmal edilecek düzeyde ise yalnızca veri alanı hesaplaması yeterlidir.
Ör: 4 bytelık tamsayı olan n elemanlı bir küme için alan maliyeti bağıntısı S(n)=4n şeklinde verilir
Alan Karmaşıklığı ( Space Complexity)
Alan karmaşıklığı eleman sayısı n’ nin çok büyük değerleri için bellek alanı gereksiniminin artış mertebesini gösteren asimptotik ifadelerdir. Bu amaçla zaman karmaşıklığında kullanılan asimptotik ifadelerle gösterilir.
Ör: Alan karnaşıklığı olarak 𝑶(𝒏 𝟐 ) verilirse bellek gereksiniminin n’nin büyük değerleri için en kötü durumda karesel arttığı ifade edilmektedir.
En İyi – Ortalama – En Kötü Durumlar (Best-Average-Worst Cases)
Yürütme zamanı, maliyet ve karmaşıklık hesaplanırken en iyi sonucun elde edildiği durum
en iyi durum (best case) dur.
En Kötü durum (worst case) ise en olumsuz koşulların gerçekleşmesi durumunda algoritmanın çözüm üretmesi için gerekli hesaplama sonucudur.
Big-O Notasyonu
Bir işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması diyebiliriz.Yada büyüme hızını gösterir de diyebiliriz.
Sık kullanılan büyüme hızları
Zaman Karmaşıklığı
|
Örnek
|
O(1) sabit
|
Bağlı listeye ilk eleman olarak ekleme yapma
|
O(log N) log
|
Sıralı bir dizide bir eleman arama
|
O(N) lineer
|
Sıralı olmayan bir dizide eleman arama
|
O(Nlog N) nlog-n
|
N elemanlı böl-parçala-yut yöntemiyle sıralama
|
O(N2) ikinci dereceden
|
Bir grafikte iki düğüm arasındaki en kısa yolu bulma
|
O(N3)
üçüncü dereceden
|
Ardarda gerçekleştirilen lineer denklemler
|
O(2N) üssel
|
Hanoi’nin Kuleleri problemi
|
Asimptotik Notasyon
Eleman sayısının sonsuza gitmesi durumunda algoritmanın, benzer işi yapan algoritmalarla karşılaştırmak için kullanılır.Verilen iki algoritmanın çalışma zamanını T1(N) ve T2(N) fonksiyonları şeklinde gösterilir. Hangisinin daha iyi olduğunu belirlemek için bir yol belirlememiz gerekiyor.
– Big-O (Big O): Asimptotik üst sınır
– Big W (Big Omega): Asimptotik alt sınır
– Big Q (Big Teta): Asimptotik alt ve üst sınır
Big O Notasyonu
Yorumlar
Yorum Gönder