computational complexity

• 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.