İçeriğe geç

Algoritma Analizi

Algoritmanın sahip olması gereken özellikler

  • Giriş/Çıkış bilgisi
  • Sonluluk
  • Kesinlik
  • Etkinlik
  • Başarım ve Performans

Algoritmaların Analizi

Aynı problemi birçok algoritma ile çözebiliriz ancak bizim için önemli olan verimliliktir. Bu nedenden dolayıda algoritmalar arasında bir kıyaslama yaparız. Bu kıyaslama genel olarak “Çalışma Zamanı”ın karşılaştırılmasıdır.

Çalışma Zamanı Analizi(Karmaşıklık Analizi) bir algoritmanın artan veri girişine bağlı olarak işleme zamanındaki değişikliğin tespit etmektirç

Kullanılacak Yöntemler

1.Deneysel Analiz Yöntemi

  • Örnek problemlerde denenmiş bir algoritmada hesaplama deneyimine dayanır.
  • Amaç; pratikte algoritmanın nasıl davrandığını tahmin etmektir.
  • Program yazılır ve problem örneklerinin bazı sınıfları üzerinde performans test edilir.
  • Bilimsel yaklaşımdan çok uygulamaya yöneliktir.

2.RAM(Random Access Machine) Modeli ile Komut Sayarak Çalışma Zamanı Analizi

  • Her basit operasyon(+,-,*,=,if,call) “bir” zaman biriminde gerçekleşir.
  • Genel olarak çalışma zamanı veri giriş boyutu n’ye bağlı olarak T(n) ile ifade edilirç
  • Dezavantajı: Algoritmanın çok detaylı şekilde implemente edilmesidir.

ÖRNEK:

Toplam Zaman=1+N+N+1=2N+2

3.Asimptotik Analiz ve Notasyon

Eleman sayısı n’nin sonsuza gitmesi durumunda algoritmanın benzer işi yapan algoritmalar karşılaştırmak için kullanılır.

-Eleman sayısının küçük olduğu durumlarda pratikte mümkün olabilir fakat birçok uygulamada mümkün değildir.

-Hangi algoritmanın daha iyi olduğunu belirlemek için sık kullanılan asimptotik notasyonlar:

-Big-O: Asimptotik üst sınır

-Big- Ω : Asimptotik alt sınır.

Big-O Notasyonu:

O notasyonu ilk olarak 1894 yılında Alman matematikçi Bachmann {tarafından|yönünden|sebebi ile|nedeni ile|vasıtası ile|sebebi ile} kullanılmış ve Landau vasıtası ile yaygınlaştırılmıştır. Bu nedenden dolayı adına Landau notasyonu ve ya Bachmann–Landau notasyonu da denmektedir. Algoritmanın en kötü durum analizini yapmak için uygulanan notasyondur. Matematiksel şekilde} şöyle tanımlanmaktadır:

f(x) ve g(x) reel sayılarda tanımlı iki fonksiyon olmak üzere, x > k olacak biçimde bir k vardır öyle ki,
|f(x)| < C*|g(x)| dir vebigo_elemanşeklinde gösterilir. Burada C ve k sabit sayılardır ve x’ten bağımsızdırlar.

Örneğin; f(n)=n4+ 100n2+10n+50 fonksiyonu Big-O notasyonuna göre karmaşıklığı g(n)=n dür.

-Literatürde sıklıkla karşılaşılan “Büyüme Oranı” fonksiyonları:

  • O(1): Sabit: Veri giriş boyutundan bağımsız gerçekleşen işlemler.
  • O(logN) Logaritmik: Problemi küçük veri parçalarına bölen algoritmalardır.
  • O(N) Lineer-doğrusal:Veri giriş boyutuna bağlı doğrusal artan.
  • O(N logN) Doğrusal çarpanlı logaritmik:Problemi küçük veri parçalarına bölen ve daha sonra bu parçalar üzerinde işlem yapar.
  • O(N2)Karesel
  • O(N3)Kübik
  • O(2n)2 tabanında üssel

Çok yakın zamanda Big-O Analiz kuralları ve nasıl çalıştığıyla ilgili bir yazı daha yayınlayacağım. Yayınladığımda buraya link’i bırakırım. İyi okumalar.

Tarih:GenelYazılım/Teknoloji

4 Yorum

  1. Bir yazılımcı olarak zevkle okudum. Bilgi paylaşımı için teşekkürler.

  2. Damla hanım emeğinize yüreğinize sağlık! her dersinizi çok güzel anlatmışsınız ben yabancıyım benim için kolay oldu bunları öğrenmek! Sizden yeni dersler bekleriz!Başarılar size

    • damlakayali damlakayali

      Teşekkür ederim. 🙂 Yenilerini elimden geldiğince yazmaya çalışıyorum İnşallah yararlı oluyordur. 🙂

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir