Herkese merhaba
bugün sizlerle
Algoritma analizi yapılma nedenlerini ve analiz edilen özellikleri, analiz yollarını konuşacağız.
OKUMA SÜRESİ: 7 dakika 47 saniye
bir algoritmanın analiz edilme sebepleri temel olarak şunlardır
1)Algoritmanın performansı nasıl?
2)bu mu diğer algoritma mı daha hızlı?
3)Daha iyisi mümkün mü? bu mudur?
bu sorulara aradığımız cevaplarda bize yardımcı olacak iki husus vardır
Algoritmanın çalışma zamanı analizi
Hafızada kapladığı alan analizi
şimdi bir başlangıç yapalım ve çalışma zamanı analizine bakalım;
Çalışma zamanı analizi (karmaşıklık analizi) bir algoritmanın artan veri boyutuna bağlı olarak işlem zamanının / süresinin nasıl arttığını (değiştiğini) tespit etmek olarak tanımlanır.
Yazdığınız bir Algoritmanın karmaşıklık analizini yapıyor olmanız, veri yapılarınızdaki verinizin büyüdüğü,
veya farklı farklı ortamlarda düşük güçlü veya bellekli makinalarda çalışırken oluşacak durumları daha önceden analiz edebilmenizi sağlar.
Karmaşıklık analizi için kullanılan başlıca yöntemler aşağıdaki gibidir.
Deneysel Analiz Yöntemi:
Örnek problemlerde denenmiş bir algoritmadaki hesaplama deneyimine dayanır.
Amacı, pratikte algoritmanın nasıl davrandığını tahmin etmektir. Bilimsel yaklaşımdan çok, uygulamaya yöneliktir. Programı yazan programcının tekniğine, kullanılan bilgisayara, derleyiciye ve programlama diline bağlı olarak değişkenlik gösterir.
RAM (Random Access Machine) Modeli:
(Komut Sayarak Çalışma Zamanını Analiz Yöntemi)
RAM modeli algoritma gerçekleştirimlerini ölçmek için kullanılan bir yöntemdir. Genel olarak çalışma zamanı veri giriş boyutu N’e bağlı T n ile ifade edilir. Her operasyon (+,-, * =, if) “bir” zaman biriminde gerçekleşir.
Her basit işlem “bir” birim zamanda gerçekleşir. Fakat döngüler ve fonksiyonlar basit işlem olarak değerlendirilmezler.
RAM modelinde her bellek erişimi yine “bir” birim zamanda gerçekleşir.
RAM modeline basit bir örnek verelim:
Algoritmalar arası analiz yaparken kıyaslamanın kolaylaşması için algoritmaların polinom veya diğer zaman karmaşıklıkları cinsinden ifade edilmesi gerekir. Bu ifadeler sonucu karşılaştırma yapılarak algoritmanın
best case (en kısa süren)
worst case (en uzun süren)
average case (ortalama süren)
durumları kıyaslanır.
Worst case (en kötü): Algoritma çalışmasının en fazla sürede gerçekleştiği analiz türüdür. En kötü durum, çalışma zamanında bir üst sınırdır ve o algoritma için verilen durumdan “daha uzun sürmeyeceği” garantisi verir. Bazı algoritmalar için en kötü durum oldukça sık rastlanır. Arama algoritmasında, aranan öğe genellikle dizide olmaz dolayısıyla döngü N kez çalışır.
Best case (en iyi): Algoritmanın en kısa sürede ve en az adımda çalıştığı giriş durumu olan analiz türüdür. bir alt sınırdır.
Average case (ortalama): Algoritmanın ortalama sürede ve ortalama adımda çalıştığı giriş durumu olan analiz türüdür.
Bir algoritmanın genelde EN KÖTÜ durumdaki çalışma zamanına bakılır.
Asimptotik Notasyon/Zaman Karmaşıklığı(Fonksiyonların Büyümesi)
Asimptotik Notasyon, eleman sayısı n’nin sonsuza gitmesi durumunda algoritmanın, benzer işi yapan algoritmalarla karşılaştırmak için kullanılır.
Algoritmamıza gelen girdi sayısı çok büyüdüğünde ve sonsuza giderken algoritmamızın nasıl davranacağını gösterir. Eğer girdi boyutu ile Big-o sonucu da çok fazla büyüyorsa ise algoritma verimsizdir diyebiliriz. Algoritmanın girdi boyutu büyüdükçe küçük kalan Big-o notasyonuna sahip olan algoritma daha iyidir.
Big O: Asimptotik üst sınır
Big Omega: Asimptotik alt sınır
Big Teta: Asimptotik alt ve üst sınır
Büyük O Notasyonu (Big O Notation)
Big O notasyonu ilk olarak 1894 yılında Alman matematikçi Bachmann tarafından kullanılmış ve Landau tarafından da yaygınlaştırılmıştır. Bundan dolayı adına Landau notasyonu da denir.
Sabit zamanlı ifadeler O(1) ile gösterilir. Örnek olarak atama işlemleri.
If-else durumunda, ifadenin if veya else bloğundaki hangi ifade karmaşıklık olarak daha büyükse O fonksiyonu o değeri döndürür.
Örneğin: f( n ) = n⁴ + 100n² + 10n + 50
algoritma fonksiyonunda g( n )= n⁴ olur
“Daha açık bir ifadeyle”, n’nin artan değerlerinde f( n )'nin maksimum büyüme oranı
g( n ) = n⁴ O( n⁴ )
Big O-notasyonu gösteriminde bir fonksiyonun düşük n değerlerindeki performansı önemsiz kabul edilir
Özetle: Donanım, işletim sistemi, derleyici ve algoritma detaylarından bağımsız, sadece büyük n değerlerine odaklanıp, sabitleri göz ardı ederek daha basit bir şekilde algoritmaları analiz etmemize ve karşılaştırmamızı sağlar.
kısacası Polinomun derecesi alınır.
BÜYÜME ORANI TABLOSU
bugün sizlerle
Algoritma analizi yapılma nedenlerini ve analiz edilen özellikleri, analiz yollarını konuşacağız.
OKUMA SÜRESİ: 7 dakika 47 saniye
bir algoritmanın analiz edilme sebepleri temel olarak şunlardır
1)Algoritmanın performansı nasıl?
2)bu mu diğer algoritma mı daha hızlı?
3)Daha iyisi mümkün mü? bu mudur?
bu sorulara aradığımız cevaplarda bize yardımcı olacak iki husus vardır
Algoritmanın çalışma zamanı analizi
Hafızada kapladığı alan analizi
şimdi bir başlangıç yapalım ve çalışma zamanı analizine bakalım;
Çalışma zamanı analizi (karmaşıklık analizi) bir algoritmanın artan veri boyutuna bağlı olarak işlem zamanının / süresinin nasıl arttığını (değiştiğini) tespit etmek olarak tanımlanır.
Yazdığınız bir Algoritmanın karmaşıklık analizini yapıyor olmanız, veri yapılarınızdaki verinizin büyüdüğü,
veya farklı farklı ortamlarda düşük güçlü veya bellekli makinalarda çalışırken oluşacak durumları daha önceden analiz edebilmenizi sağlar.
Karmaşıklık analizi için kullanılan başlıca yöntemler aşağıdaki gibidir.
Deneysel Analiz Yöntemi:
Örnek problemlerde denenmiş bir algoritmadaki hesaplama deneyimine dayanır.
Amacı, pratikte algoritmanın nasıl davrandığını tahmin etmektir. Bilimsel yaklaşımdan çok, uygulamaya yöneliktir. Programı yazan programcının tekniğine, kullanılan bilgisayara, derleyiciye ve programlama diline bağlı olarak değişkenlik gösterir.
RAM (Random Access Machine) Modeli:
(Komut Sayarak Çalışma Zamanını Analiz Yöntemi)
RAM modeli algoritma gerçekleştirimlerini ölçmek için kullanılan bir yöntemdir. Genel olarak çalışma zamanı veri giriş boyutu N’e bağlı T n ile ifade edilir. Her operasyon (+,-, * =, if) “bir” zaman biriminde gerçekleşir.
Her basit işlem “bir” birim zamanda gerçekleşir. Fakat döngüler ve fonksiyonlar basit işlem olarak değerlendirilmezler.
RAM modelinde her bellek erişimi yine “bir” birim zamanda gerçekleşir.
RAM modeline basit bir örnek verelim:
Algoritmalar arası analiz yaparken kıyaslamanın kolaylaşması için algoritmaların polinom veya diğer zaman karmaşıklıkları cinsinden ifade edilmesi gerekir. Bu ifadeler sonucu karşılaştırma yapılarak algoritmanın
best case (en kısa süren)
worst case (en uzun süren)
average case (ortalama süren)
durumları kıyaslanır.
Worst case (en kötü): Algoritma çalışmasının en fazla sürede gerçekleştiği analiz türüdür. En kötü durum, çalışma zamanında bir üst sınırdır ve o algoritma için verilen durumdan “daha uzun sürmeyeceği” garantisi verir. Bazı algoritmalar için en kötü durum oldukça sık rastlanır. Arama algoritmasında, aranan öğe genellikle dizide olmaz dolayısıyla döngü N kez çalışır.
Best case (en iyi): Algoritmanın en kısa sürede ve en az adımda çalıştığı giriş durumu olan analiz türüdür. bir alt sınırdır.
Average case (ortalama): Algoritmanın ortalama sürede ve ortalama adımda çalıştığı giriş durumu olan analiz türüdür.
Bir algoritmanın genelde EN KÖTÜ durumdaki çalışma zamanına bakılır.
Asimptotik Notasyon/Zaman Karmaşıklığı(Fonksiyonların Büyümesi)
Asimptotik Notasyon, eleman sayısı n’nin sonsuza gitmesi durumunda algoritmanın, benzer işi yapan algoritmalarla karşılaştırmak için kullanılır.
Algoritmamıza gelen girdi sayısı çok büyüdüğünde ve sonsuza giderken algoritmamızın nasıl davranacağını gösterir. Eğer girdi boyutu ile Big-o sonucu da çok fazla büyüyorsa ise algoritma verimsizdir diyebiliriz. Algoritmanın girdi boyutu büyüdükçe küçük kalan Big-o notasyonuna sahip olan algoritma daha iyidir.
Big O: Asimptotik üst sınır
Big Omega: Asimptotik alt sınır
Big Teta: Asimptotik alt ve üst sınır
Büyük O Notasyonu (Big O Notation)
Big O notasyonu ilk olarak 1894 yılında Alman matematikçi Bachmann tarafından kullanılmış ve Landau tarafından da yaygınlaştırılmıştır. Bundan dolayı adına Landau notasyonu da denir.
Sabit zamanlı ifadeler O(1) ile gösterilir. Örnek olarak atama işlemleri.
If-else durumunda, ifadenin if veya else bloğundaki hangi ifade karmaşıklık olarak daha büyükse O fonksiyonu o değeri döndürür.
Örneğin: f( n ) = n⁴ + 100n² + 10n + 50
algoritma fonksiyonunda g( n )= n⁴ olur
“Daha açık bir ifadeyle”, n’nin artan değerlerinde f( n )'nin maksimum büyüme oranı
g( n ) = n⁴ O( n⁴ )
Big O-notasyonu gösteriminde bir fonksiyonun düşük n değerlerindeki performansı önemsiz kabul edilir
Özetle: Donanım, işletim sistemi, derleyici ve algoritma detaylarından bağımsız, sadece büyük n değerlerine odaklanıp, sabitleri göz ardı ederek daha basit bir şekilde algoritmaları analiz etmemize ve karşılaştırmamızı sağlar.
kısacası Polinomun derecesi alınır.
BÜYÜME ORANI TABLOSU
ZAMAN KARMAŞIKLIĞI | AÇIKLAMA | ÖRNEK |
O(1) | Sabit: Yenilmez! | Bağlı listeye ilk eleman olarak ekleme yapma |
O(log N) | Logaritmik: Problemi küçük veri parçalarına bölen algoritmalarda görülür. | Binary search, tree veri yapısı üzerinde arama |
O(N) | Lineer – doğrusal: Hızlı bir algoritmadır. N tane veriyi girmek için gereken zaman | Sıralı olmayan bir dizide bir eleman arama |
O(N log N) | Doğrusal çarpanlı logaritmik: Problemi küçük veri parçalarına bölen ve daha sonra bu parçalar üzerinde işlem yapan. | N elemanı böl-parçala-yönet yöntemiyle sıralama. Quick Sort. Çoğu sıralama algoritması bu gruptadır. |
O(N²) | Karesel: Veri miktarı azsa uygun (n<1000) | Bir grafikte iki düğüm arasındaki en kısa yolu bulma veya Buble Sort. |
O(N³) | Kübik: veri miktarı azsa uygun (n<1000) | Ardarda gerçekleştirilen lineer denklemler |
O(2ⁿ) | İki tabanında üssel. Veri çok azsa uygun (N<=20) | Hanoi’nin Kuleleri problemi |
şimdi örneklere geçelim:
(iterasyon kelimesi: tekerrür, tekrarlama, yineleme ve mükerrer anlamlarına gelmektedir)
SIK YAPILAN HATALAR!
1)Karmaşıklığı bulmak için sadece döngüleri saymakla yetinmeyin.
2) 2 içi içe döngünün 1 den N² kadar döndüğünü düşünürsek karmaşıklık O(N⁴) olur.
3) O(2N²) veya O(N²+N) gibi ifadeler kullanmayın.
Sadece baskın terim kullanılır ve öndeki sabitler kaldırılır
4) İç içe döngüler karmaşıklığı direk etkilerken art arda gelen döngüler karmaşıklığı etkilemez.
son olarak RAM yönteminden O( n )dönüşümüne örnek vermek istiyorum:
1) 4n² - 3n log n + 17.5 n - 43 n⅔ +75
2) n² – n log n + n - n⅔ + 1 sabitleri atalım
3) n² sadece büyük n değerlerini alalım
sonuç: O(n²)
