• çeşitli algoritmaların bu analiz yöntemi ile verimliliklerinin ve karmaşlıklıklarının (complexity) bulunması konusuna verilen isimdir. knuth'un bu konuda çok önemli çalışmaları ve katkıları vardır. neredeyse her bilgisayar mühendisliği veya computer science bölümünde herhangi bir dersin altında bulunan konudur.
  • (bkz: final dönemi entryleri)
  • aile parasıyla iphone alırken masraf düşünmeyenlere problem çözmek için masraf hesaplattırır*.
  • bilgisayar mühendisliğinde gösterilen teorik derslerin başında gelir. matematik altyapınız iyiyse, bu dersi öğrenmek pek zor değildir.
  • hesaplanabilir işlemler, adımlar ya da adım dizilerinin bir cebir üzerindeki 'büyüklüğü' (normu) üzerinden sınıflandırılabilir. örneğin iki -uyumlu- kare matris çarpımı için gerekli adım dizisi (nokta çarpım silsilesi: çarp, biriktir/sakla/diz, topla), -eğer herhangi bir özelleştirme ya da bellek organizasyonu/gösterimsel iyileştirme yok ise- boyutun küpü ile ifade edilir. dolayısıyla algoritma analizi, söz konusu büyüklüklerin ifade edilmesini, olanaklı ise hesaplanmasını, sonuçların yorumlanmasını ve çeşitli organizasyonel geliştirmelerle aynı çıktıyı üretecek biçimde 'iyileştirilmesini' kapsayan konu başlığıdır.
  • olan bir algoritmanın zaman ve space(uzay) karmaşıklığının bulunmasıdır. bir algoritmanın zaman karmaşıklığı yani problemi ne kadar hızlı olduğu hesaplanırken tabii ki de kullanılan veri yapıları çok önemli. eğer algoritmanız bir elemena erişecekse bunu da belli bir zaman karmaşıklığında yapar yani aynı işlemleri yapan bir algoritma kullanılan veri yapılarına göre verimliliği değişir. özet olarak algoritma analizini anlayabilmek için veri yapıları(dizi, ağaç yapıları , sıralı listeler vb.) bilmeniz gerekir.
  • şimdi bi kod yazdınız ama kodunuzun ne kadar kaynak tükettiğini bilmiyorsunuz. bunu hesaplamak için kullandığınız yöntemlere algoritma analizi deniyor.

    kaynağımız iki tane, time ve space. kodunuzun (veya işte algoritmanızın) time complexity ve space complexity'sini hesaplarsanız, ne kadar kaynak tüketeceğini oradan hesaplayabiliyorsunuz.

    fakat gördüğünüz gibi hesapladığımız şey kompleksite. direkt olarak "abi bu kod 15 saniyede çalışıyor" demek pratik değil, çünkü o kod yarın başka bir bilgisayarda, başka bir cpu'da, başka bir veri setiyle çalışabilir. onun yerine, işlediğiniz verinin büyüklüğüne * oranla hesaplama yapıyorsunuz. bu hesabın gösterildiği formata da big-o notation deniyor. şimdi örnek vericem daha anlaşılır olacak her şey.

    diyelim ekşi'deki bir başlıkta en fazla fav alan yazıyı bulacak bi kod yazmanız gerekiyor olsun. elimizde bir liste var, listenin her elemanı bir tuple, ilk eleman yazının id'sini, ikinci eleman da yazının fav sayısını veriyor olsun. birisi html'den bu bilgileri çıkarıp listeye koyacak kodu yazmış yani, bize de en favlısını bulma işi kalmış. elimizde şöyle bi array var yani:

    [ (id: 5, fav: 10), (id:12, fav: 20), (id: 75, fav: 0) ]

    yani başlıkta 3 tane yazı var, id'leri sırasıyla 5, 12, 75, fav sayıları da sırasıyla 10, 20 ve 0. en sondaki favsız entry benim politik entry'lerimden biri :(((

    şimdi ne yapcaz, fav sayısı en fazla olan entry'i bulmamız lazım. bu yüzden listenin elemanlarına tek tek bakıyoruz, bi değişkende max değeri tutuyoruz, eğer listeden o an baktığımız elemanın fav sayısı, max'tan daha büyükse artık max değer o an baktığımız eleman oluyor. liste bitince de elimizdeki max değeri dönüyoruz. dümdüz basit kod. peki bunun algoritmik karmaşıklığı nedir?

    space complexity'miz direkt olarak o(1). niye? çünkü space complexity hesabı, input size'a ek olarak kullandığımız yeri göstermek için kullanılıyor. elemanları bi yere kopyalamadık, sadece max değeri tuttuğumuz 1 adet değişkenimiz var.

    time complexity nedir? o da o(n). çünkü listedeki en büyük elemanı bulmak için bütün elemanlara tek tek bakmamız gerekiyor. örnekte ikinci entry en favlı, ama belki başka başlıkta en çok fav alan entry en son girilen entry'dir? hepsine bakmadan emin olamayacağımız için bütün listeyi gezmemiz, bütün elemanları kontrol etmemiz gerekiyor. n tane eleman için n tane işlem yapmamız gerektiğine göre time complexity'miz o(n)'dir diyoruz.

    peki eğer bizden en çok fav alanı değil de, en az fav alan entry'i bulmamız istense ne olacaktı?

    burada elimizde ekstra bir bilgi var. herhangi bir entry'nin fav sayısı en düşük 0 olabilir, negatif bir sayı olamaz. bu ekstra bilgi, algoritmanın zaman karmaşıklığını komple değiştiriyor (space complexity hala aynı, çünkü elimizde liste var, kopyalamaya gerek yok vs.). şimdi elimizde 2 ihtimal var:

    1- worst case. listede 0 favlı bir eleman yok. varsa da listenin en sonunda. bu durumda yine bütün elemanlara tek tek bakacağız, dolayısıyla karmaşıklığımız hala o(n). genelde en çok dikkate aldığımız case budur, çünkü en kötü senaryoda başımıza ne gelebilir burada görüyoruz.

    2- best case. listeye bakmaya başladık, ama o da ne? ilk entry sıfır fav'lı. tatava yapmayıp o elemanı dönüyoruz. listenin uzunluğu n olsa bile tek işlemde aradığımız elemanı bulduk. bu yüzden karmaşıklığımız o(1).

    bir de average case var gerçi ama o olasılık hesabına giriyor, o yüzden o da başka bir entry'nin konusu olsun.
hesabın var mı? giriş yap