-
-
(bkz: np hardness)
-
ing. hesaplama karmasikligi
-
bir algoritmanın çalışma süresinin, girdi boyunun fonksiyonu cinsinden ifade edilmesidir. açmak gerekirse, elimizde bir problem olsun. p diyelim. bu problemi deterministik olarak çözebilen bir algoritmamız olsun, ona da a diyelim. böyle bir algoritma çözüm önerisi olarak geliştirildiğinde, ilk etapta emin olunması gereken iki husus vardır. birincisi doğruluk, ikincisi hesaplama karmaşıklığı. doğruluğunun ispatlanması, başka bir başlıkta incelenmelidir.
hesaplama karmaşıklığı ise şu açıdan önemlidir, bu problem sınıfına giren problem örneklerinin girdi boyu arttıkça, önerdiğimiz algoritmanın tamamlanma süresi ne kadar hızlı artıyor?
bu bağlamda, algoritma polinomyal veya eksponansiyel olarak iki sınıfa ayrılabilir. polinomyal demek, problem örneği, n boyunda ise, algoritma n'nin bir sabit kuvveti (örneğin n^k, k bir sabit) süresinde tamamlanır. eğer a algoritması, bir sabitin n kuvveti süresinde tamamlanıyorsa, buna da eksponansiyel karmaşıklık denir (örneğin k^n, k bir sabit ve k>1). bu iki karmaşıklık sınıfını karşılaştırmak gerekirse, k sabitine en basitinden 2 diyelim. n^2 polinomyal bir karmaşılık iken, 2^n eksponansiyeldir. ve n sayısı, yani problem örneğinin boyu arttıkça, ikinci fonksiyon, birinciden çok daha hızlı büyür. dolayısıyla, teorik olarak eksponansiyel karmaşıklığında algoritmalar önerilse de, pratikte pek uygulanmazlar çünkü gerçek hayattaki problemlerin çok büyük bir çoğunuğunda, n, algoritmanın, bir insan ömründen daha kısa sürede tamamlanmasına müsade etmeyecek kadar büyüktür.
exponansiyelden daha ötede n! (faktoryel) karmaşıklığı, onun da ötesinde n^n kamaşıklığı vardır ki bunlar zaten pratikte düşünülemeyecek karmaşıklıktaki bazı algoritmaların durumunu ifade eder.
bu konuyla ilgili bir önemli husus da, bir algoritma kamaşıklığının büyük o, büyük omega, büyük teta, veya küçük o, küçük omega cinsinden ifade edilmesidir. bu da, bir algoritmanın karmaşıklık ifadesi elimizde olsa bile o algoritmayı pratiğe dökmeden, gerçek zaman ifadesi ile ne kadar süreceğini söyleyemeyeceğimiz anlamına gelir. o zaman insanın aklına şu soru geliyor, madem ne kadar süreceğini saniye/dakika/saat/gün gibi takvim birimleri kullanarak hesaplayamıyorsak, o zaman ne anlamı var bu kadar uğraşmanın?
çok bilinen iki sıralama algoritmasından örnek vererek, nedenini görmeye çalışalım. biri insertion sort, diğeri radix sort.
ikisi de sıralama algoritmasıdır. insertion sort, n^2 karmaşıklığında çalışıp, literatürdeki en yavaş sıralama algoritması olarak geçer. radix sort, biraz daha mızmız olup, fazladan kısıt gerektir ama kamaşıklığı n cinsindendir.
yani 10 elemanlı bir diziyi insertion sort örneğin 100 saniyede sıralıyorsa, radix sort 10 saniyede sıralar (bu örnek için her iki algoritmanın da gerçeklenmelerinden kaynaklanan sabitlerin, aynı olduğu varsayılmıştır). 10 saniye ile 100 saniye arasında çok bir fark yok sanırım. ama 1000 elemanlı bir dizi elimize geçtiğin radix sort, 1000 saniye sürerken (16-17 dakika arası), insertion sort, 1000000 saniye yani neredeyse 2 yıl kadar sürer. sanıyorum bu örnek, neden n karmaşıklığındaki bir algoritmanın n^2 karmaşıklığındaki bir algoritmaya tercih edileceğini göstermiştir. bu yüzden bir algoritma buldunuz ve karmaşıklığını hesapladınız mı, aynı problemi çözen diğer algoritmalarla karşılaştırın, eğer karmaşıklıkta daha iyi ise, o zaman süper bir iş yapmışsınız demektir. yok eğer daha önce çözülememiş bir probleme çözüm mü buldunuz, o zaman karmaşıklığı polinomyalse, muhtemelen çok ünlü olacaksınz
-
olayın teorisi biraz karmaşık* olduğundan aklın dehlizlerine ulaşmak maksadıyla basite indirgemeye çalışacağım. başaramazsam kızmayın, oluyor genelde. başarısızlık ben de sık tekrar eden uykusuzluk hali. neyse konumuza dönelim.
hesaplama karmaşıklığı probleminizin zaman* ve uzay* karmaşıklığının boyutunu/miktarını ifade eder. bir problem zaman ve uzay karmaşıklığını aza indirgemek amacıyla matematiksel adımlarla çözüm için algoritma kullanmayı gerektiriyorsa, bu problem doğal olarak zor kabul edilir. problemi çözmek için gerekli olan zaman ve hafıza kaynakların miktarı bazı sezgisel yöntemlerle formülize edilir. diğer karmaşıklık ölçütleri ise iletişim miktarı ve işlemci sayısı karmaşıklığıdır. bu ölçütler de matematiksel çözüm karmaşıklığı ifade ederken kullanılır. bilgisayarın neleri yapıp yapamayacağının bilinmesi de hesaplama karmaşıklığında rol oynamaktadır. burada bilgisayar biliminin teorisi hesaplama karmaşıklığıyla yakından ilişkilidir. bilgisayarımız kısıtlı kaynaklarla çözülemez problemleri sınıflandırmak için kullanılır. olayın teorisi bilgisayarın sınıflandırmasıyla yakından ilişkilidir. hesaplama teorisini hesaplama karmaşıklığından ayıran tam olarak mevcut kaynakların durumudur.
düzeltme: şunu da ekleyelim; (bkz: heuristic/#60229000)
-
ulan sunun hesaplamasini anlamak icin 1 yilimi harcadim. ne universitede acikladilar ne de internette dogru duzgun bir aciklayan yer gordum. sayesinde google'dan da red yedik, neymis 2 tane nested for loopun o(n^2) oldugunu bilemeyecek adami staja almazlarmis (adam aklimi karistirdi ha basta n^2 demistim ben, daha sonra n/2 den falan n dir gibi bisey dedim ki o kismini sormayin zaten).
gidipte aptal saptal terminolojiye girmeden, matematigine de girmeden anlatayim millet rahatcana anlasin sunu ya.
simdi arkadas bunu nasil mi hesapliyoruz, bu aslinda herhangi bir islemin ne kadar zamanda surecegini harflerle bulma yontemidir. gunumuzde hemen hemen cogu matematiksel hesaplama veya program fonksiyonlari 1 veya sabit sayili cpu cycle ile olur. ornegin 20 hz lik bir cpu muz olsun ve toplama islemi 20 cpu cycle yani 20 hz olsun. 5+3 islemi tam 1 saniye surer. biz bu durumda toplama islemine o(20) diyebiliriz, fakat bir kural var, o da herhangi bir sabit sayiyi 1 e sadelestirebilirsin. bu durumda o(20) = o(1) dir.
durum boyle oldugu icin, cogu zaman bu hesaplamalardaki ana hesapladigimiz sey dongulerdir. misal ustteki gibi toplama yapacagiz fakat bu sefer n diye bir arrayimiz olsun, ve n arrayindeki her sayiyi 5 ile toplayacagiz. bu durumda n arrayinin sayisi kadar toplama islemi yapmis oluruz. n arrayi ne kadar buyur kuculur bilmiyorsak boyle bir algoritmanin coplexity si o(n) deriz.
ustteki sabit olaya da gelirsek, mesela diyelim ki her 2 ye bolunen arrayin indexini sadece 5 ile toplayacagiz, bunu iki islem olarak yapalim. 1. islemde, yeni bir m arrayimiz olsun ve bu m arrayine sadece 2 ile bolunen indexin sayilari koyalim. bir sayinin 2 ile bolunup bolunmedigini anlamak icin if (i % 2) gibi birsey kullaniriz burda % isleminin de o(1) tuttugunu varsayalim. simdi bu islem sonucu o(n) tuttu yine. gelelim bir sonraki isleme, bu sefer m arrayini donguye alip topluyoruz. simdi bunun da sonucu o(m) etti. fakat m arrayinin boyutu teknik olarak n/2 eder. o zaman buna biz o(n/2) de diyebiliriz. fakat bu ikinci islemi ayni zamanda o(n) diye sadelestirebiliriz. simdi gelelim asil toplam isleme. simdi ilk islemimiz o(n) idi, ikincisi ise o(m) idi. o(n)+o(m) = o(n+m) bunu burda birakmak yerine devam etmeliyiz cunku m in aslinda n/2 oldugunu biliyoruz, o(n+m) = o(n+ (n/2)) = o(n+(n/1)) = o(n+n)=o(2n) =o(n) diyerek o(n) i buluruz.
gelelim simdi diger olaya, diyelim ki bu n arrayindeki sayiyi diger butun sayilarla toplayip, toplam her sayinin toplamini alacagiz. ılk akla gelen cozum:
int toplam = 0;
for (int i = 0; i< n.size(); i++) {
for (int j = 0; j < n.size(); j++) {
if (i == j) {continue;}
n[i]+=n[j];
}
toplam+=n[i];
}
gibi birsey olur, burda iki tane ic ice dongu var, once for j li kisma bakalim sirf o kisim o(n) tutuyor. simdi for i li kisma baktigimizda onda da ayni array uzerinde dongu yapiyoruz. her bir n deki eleman icin o(n) adet islem yaptigimiz icin, ve for i de o(n) tuttugu icin o(n)*o(n) gibi birsey diyebiliriz, bu da o(n*n) den o(n^2) yapar.
gordugunuz uzere bu taz dongulere (looplara) nested loop diyoruz. yani ic ice donguler. bu tarz donguler kesinlikle verimsizdir. mumkun oldugunca ayirmaya calisin.
simdi gelelim isin google lik kismina. e bunu yaptin sen, daha optimize edemezmisin?
tabi edelim, simdi ne biliyoruz. her sayiyi topluyoruz dimi, bu toplama islemini de n in sayisi kadar yapiyoruz, ve hepsinde de kendisi haric diger sayilarla topluyoruz. yani her islem sonucu aslinda toplama eklenen sayi ayni. o zaman:
int toplam = 0;
for (int i = 0; i< n.size(); i++) {
toplam+=n[i];
}
diyebiliriz. bu islem o(n) tutuyor. simdi toplami icin toplam n in adeti kadar yapabiliriz:
for (int i = 1; i< n.size(); i++) {
toplam+=toplam;
}
(bunun yerine toplam*=n.size() demek gercek hayatta daha verimli yapar ama bu konuda daha verimli yapmaz)
simdi bu islemde o(n-1) etti.
elimizde 2 tane islem var hemen sadelestirelim o(n)+o(n-1) = o(n+n-1) = o(2n-1) = o(2n) = o(n).
gordugunuz gibi olay bu kadar basit.
su noktayi da atlamayayim, herkes icin her complexity dogru veya yanlis degildir, bu konuda kesinlik yok. yani sen benim bu algoritmamin complexity si o(n) dersin, baska bir adam hayir o(n^2) diyebilir ve ikinizin verdigi cevapta dogru olabilir. bunun nedeni tamamen varsayimlara dayali olmasi, hemen hemen herseyi varsaymaniz gerekiyor. misal ustte dedigim toplama islemini ben o(1) diye varsaymasaydim, direkt konuya dalip buyrun o(n) de bu soruyu cozdum deseydim, baska birisi hayir toplama islemlerinin o(n) tuttugunu varsayarsak o(n^2) oluyor diyebilir.
simdi hadi bakalim, google'a staja basvurabilirsiniz. kiyagimi unutmayin koftehorlar.