1-) YETERLİLİK KONULAR - ALGORİTMALAR

Algoritma nedir?

belirli bir problemi çözmek için adım adım uygulanan kurallar dizisidir.

Algoritma aşamaları ?

=> Analiz: veri yapılarını ayarlama

=> Tasarım: İçeriğini oluşturma

=> Uygulama: Kodlama

=> Test Etme:  Doğruluğunu test etme

Neden algoritmayı analiz ederiz?

Algoritmanın performansını ölçmek için

Farklı algoritmalarla karşılaştırmak için

Daha iyisi mümkün mü? olabilecek en iyisi mi? sorularını cevaplamak için

Algoritmanın etkinliği(performansı)

1) Zaman karmaşıklığı (iç faktör): Algoritmanın zaman gereksinimi, program işletim süresi

2) Bellek karmaşıklığı (iç faktör): Algoritmanın bellek gereksinimi, programın işletildiği sürece gerekli olan yer miktarına denilir. Bellek karmaşıklığının komut, veri ve çevresel yığın uzayı olmak üzere 3 bileşeni vardır.

Komut alanı: Program komutlarının derlenmiş halinin depolanması için gerekli alandır

Veri alanı: Tüm sabit ve değişkenlerin depolanması için gerekli alandır.

Yığın alanı: Fonksiyonların kaldığı yerden çalışması için gerekli bilgilerin saklandığı alandır.

3) Dış faktörler: girdi verisinin büyüklüğü, Pc hızı, Derleyci kalitesi

ALGORİTMADA KARMAŞIKLIK(COMPLEXİTY) VE ZAMAN KARMAŞIKLIĞI ANALİZİ

Every-Case Running Time:

 Harcanan zaman yalnızca giriş boyutuna bağlıdır.

Örn: dizi elemanlarının toplanması => Dizideki elemanların değerinin önemi olmaksızın döngü n defa döner

Worst-Case Running Time:

Programın en kötü ihtimalle ne kadar süreceğini tahmin etmek için kullanılır. Harcanan zaman hem giriş boyutuna hemde giriş değerine bağlıdır.

Örn: Arama algoritmalarının en kötü durumu aranan elemanın dizide bulunamaması

Dizideki bir elemanın arananan eleman x ile kıyaslanması

W(n)=n ->worst-case -> elemanın bulunamaması

İnsertion Sortun en kötü durumu rastgele sıralanmış olmasıdır.

W(n)=n²

Average-Case Running Time:

Algoritmanın ortalama olarak ne kadar sürede gerçekleştiği, işletim süresi, her girdi boyutundaki tüm girdilerin ortalamasıdır.

n*(n+1)/n = n+1

Best-Case Running Time:

Algoritmanın en iyi ne kadar sürede gerçekleştiği

Örn: Aranan değerin ilk adımda bulunması

Asimptotik Analiz:

Girdi boyutu sonsuza yaklaşırken işletim süresinin ne kadar az gösterdiği asimtotik notasyonlarla ifade edilir. Algoritmanın iç detaylarına bakılarak, sabit çalışma zamanı komutları göz ardı edilerek algoritmanın çalışma zamanı bir matematiksel özdeşlik olarak yazılabilir.

Asimptotik analizin elemanı olan 4 önemli gösterim:

o-notation

Big O-notation

Omega - notasyon

Q notasyon