Algoritmalarda Karmaşıklık Hesabı

İyi Algoritma Ne Demektir?

█ Etkinlik

█ Çalışma Zamanı

█ Bellek Kullanımı

Algoritmaları karşılaştırırken daha çok çalışma zamanı ölçütü kullanılacaktır. İstenen ise çalışma zamanını giriş boyutuna bağlı olarak belirleyen bir yöntem bulmak.

                 

• 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ü? Olabileceklerin en iyisi mi?

• Özelliklerinin analizi

– Algoritmanın çalışma zamanı

– Hafızada kapladığı alan

Çalışma Zamanı Analizi (Big-O, Order of Magnitude)

Büyük-O nasıl hesaplanır?

Read More

İkili ağaçlar nedir, ikili arama ağaçları nedir, bu ağaçlarda dolaşma algoritmaları hangileridir, hangisi sıralı çıkış verir?

Bilgisayar bilimlerinde yer alan önemli veri yapılarından bir tanesi de ağaçlardır. Ağaç yapılarını önemli yapan özellikler:

·         Esneklik: Tek bir amaç için en iyi çözüm ağaç yapısı olmasa da, çoklu çözümler için ağaç yapısının esnekliği bu yapının avantajı olarak sayılabilir.

·         Etkili Arama: Arama sırasında ağacın bazı dalları budanarak arama yapılması performans artışı sağlar ve bu da verimliliği arttırır. Ağaç yapısı genellikle bilginin istenilen bölümüne konumlanmak için genellikle filtreleme aracı olarak kullanılır.

·         Doğal Temsil: Bilgiyi temsil etmenin doğal bir yoludur.

·         Ağaç yapısı bir uygulamayı bazen daha kolay uygulanabilir bir hale dönüştürür.

Bağlı listeler, yığıtlar ve kuyruklar doğrusal (linear) veri yapılarıdır. Ağaçlar ise doğrusal olmayan belirli niteliklere sahip iki boyutlu veri yapılarıdır (Şekil 1). Ağaçlardaki düğümlerden iki veya daha fazla bağ çıkabilir. İkili ağaçlar (binary trees), düğümlerinde en fazla iki bağ içeren (0,1 veya 2) ağaçlardır. Ağacın en üstteki düğümüne kök (root) adı verilir.

 

Şekil 1 : Bir ikili ağacın grafiksel gösterimleri

Şekil 1'de görülen ağacın düğümlerindeki bilgiler sayılardan oluşmuştur. Her düğümdeki sol ve sağ bağlar yardımı ile diğer düğümlere ulaşılır. Sol (leftptr) ve sağ (rightptr) bağlar boş ("NULL" = "/" = "\") da olabilir. Düğüm yapıları değişik türlerde bilgiler içeren veya birden fazla bilgi içeren ağaçlar da olabilir. Doğadaki ağaçlar köklerinden gelişip göğe doğru yükselirken veri yapılarındaki ağaçlar kökü yukarıda yaprakları aşağıda olacak şekilde çizilirler.

Şekil 2'deki ağaç, A düğümü kök olmak üzere 9 düğümden oluşmaktadır. Sol alt ağaç B kökü ile başlamakta ve sağ alt ağaç da C kökü ile başlamaktadır. A'dan solda B'ye giden ve sağda C'ye giden iki dal (branch) çıkmaktadır.

 

Şekil 2 : Ağaçlarda düzeyler

 Tanımlar (Örnekler Şekil 2'ye göre verilmiştir) :

1)      İkili Ağaç (Binary Tree) : Sonlu düğümler kümesidir. Bu küme boş bir küme olabilir (empty tree). Boş değilse şu kurallara uyar.

i) Kök olarak adlandırılan özel bir düğüm vardır.

ii)                 Her düğüm en fazla iki düğüme bağlıdır.

iii)               Kök hariç her düğüm bir daldan gelmektedir.

iv)               Tüm düğümlerden yukarı doğru çıkıldıkça sonuçta köke ulaşılır.

2)      Düğüm (node) : Ağacın her bir elemanına düğüm adı verilir. Örnekler : A, B, C.

3)      Kök (root) : Düzey 0'daki (şemanın en üstündeki) tek düğüm. Örnek : Şekil 2'de A bilgisini içeren düğüm.

4)      Çocuk (child) : Bir düğümün sol ve sağ bağı aracılığı ile bağlandığı düğümler o düğümün çocuklarıdır. Örnek : B ve C, A'nın çocuklarıdır.

5)      Parent : Bir düğüm, sağ ve sol bağları ile bağlandığı düğümlerin parent'ıdır. A düğümü, B ve C düğümlerinin parent'ıdır.    

6)      Bir düğümün düzey (level) veya derinliği (depth) : Bir düğümün kök düğümden olan uzaklığıdır. Örnek : D düğümünün düzeyi veya derinliği 2'dir.

7)      Ağacın derinliği (depth of tree) : En derindeki yaprağın derinliği veya yüksekliği (height). Örnek : Şekil 2'deki ağacın derinliği 3'tür.

8)      Yaprak (leaf) : Sol ve sağ bağı boş olan düğümlere yaprak adı verilir. Örnekler : D,G,H,I.

9)      Kardeş (sibling, brother) : Aynı parent'a sahip iki düğüme kardeş düğümler adı verilir. Örnekler : B ile C kardeştir. D ile E kardeştir. H ile I kardeştir.

10)  Ancestor (üst düğüm) : Bir düğümün parent'ı birinci ancestor'ıdır. Parent'ın parent'ı (recursion) ikinci ancestor'ıdır. Kök, kendi hariç tüm düğümlerin ancestor'ıdır.

11)  Descendant (alt düğüm) : Bir düğümün iki çocuğu birinci descendant'larıdır. Onların çocukları da ikinci descendant'larıdır.   

12)  Full binary tree : i) Her yaprağı aynı derinlikte olan ii) Yaprak olmayan düğümlerin tümünün iki çocuğu olan ağaç Full (Strictly) Binary Tree'dir (İkinci şart yeterli). Bir full binary tree'de n tane yaprak varsa bu ağaçta toplam 2n-1 düğüm vardır.

13)  Complete binary tree : Full binary tree'de yeni bir derinliğe soldan sağa doğru düğümler eklendiğinde oluşan ağaçlara Complete Binary Tree denilir. Böyle bir ağaçta bazı yapraklar diğerlerinden daha derindir. Bu nedenle full binary tree olmayabilirler. En derin düzeyde düğümler olabildiğince soldadır. 

14)  General Tree (Ağaç) : Her düğümün en fazla iki çocuğu olabilme sınırı olmayan ağaçlardır.

15)  İkili Arama Ağacı (Binary Search Tree) : Boş olan veya her düğümü aşağıdaki şartlara uyan anahtara sahip bir ikili ağaçtır :

i)                    Kökün solundaki alt ağaçlardaki (eğer varsa) tüm anahtarlar kökteki anahtardan küçüktür.

ii)                  Kökün sağındaki alt ağaçlardaki (eğer varsa) tüm anahtarlar kökteki anahtardan büyüktür.

iii)                Sol ve sağ alt ağaçlar da ikili arama ağaçlarıdır.

İkili Ağaçlar ve İkili Ağaçlar Üzerindeki Dolaşma İşlemleri

Dolaşma (traverse), ağaç üzerindeki tüm düğümlere uğrayarak gerçekleştirilir. Ağaçlar üzerindeki dolaşma işlemleri, ağaçtaki tüm bilgilerin listelenmesi veya başka amaçlarla yapılır. Doğrusal veri yapılarında baştan sona doğru dolaşmak kolaydır. Ağaçlar ise düğümleri doğrusal olmayan veri yapılarıdır. Bu nedenle farklı algoritmalar uygulanır. Çok bilinen yöntemler üç tane olup özyinelemeden yararlanırlar :

1)      Preorder (depth-first order) Dolaşma (Traversal)

i)                    Köke uğra (visit)

ii)                  Sol alt ağacı preorder olarak dolaş.

iii)                Sağ alt ağacı preorder olarak dolaş.

2)      Inorder (Symmetric order) Dolaşma

i)                    Sol alt ağacı inorder'a göre dolaş

ii)                  Köke uğra (visit)

iii)                Sağ alt ağacı inorder'a göre dolaş.

3)      Postorder Dolaşma

i)                    Sol alt ağacı postorder'a göre dolaş

ii)                  Sağ alt ağacı postorder'a göre dolaş.

iii)                Köke uğra (visit)

Şekil 3 : İkili Ağaç ve değişik şekillerde dolaşılması

İkili Arama Ağaçları

İkili arama ağaçları, her bir düğümün solundaki (sol alt ağacındaki) tüm düğümler kendisinden küçük, sağındakiler (sağ alt ağacındakiler) de kendisinden büyük olacak şekilde oluşturulurlar (Şekil 4). İkili arama ağaçlarındaki en önemli işlemlerden birisi aramadır.

Örnek olarak aşağıdaki ağaçta, 44 sayısını aratmak için şu işlem sırası izlenir :

Karşılaştırma 1            : 44, 47 ile karşılaştırılır. 44<47 olduğundan sol bağdan ilerlenir.

Karşılaştırma 2            : 44, 25 ile karşılaştırılır. 44>25 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 3            : 44, 43 ile karşılaştırılır. 44>43 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 4            : 44 == 44. Aranan anahtar değeri ağaçta bulundu!

Örnek olarak aşağıdaki ağaçta, 90 sayısını aratmak için şu işlem sırası izlenir :

Karşılaştırma 1            : 90, 47 ile karşılaştırılır. 90>47 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 2            : 90, 77 ile karşılaştırılır. 90>77 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 3            : 90, 93 ile karşılaştırılır. 90<93 olduğundan sol bağdan ilerlenir.

            : NULL. Aranan anahtar değeri ağaçta bulunamadı.

Şekil 4 : İkili Arama Ağacı

Görüldüğü gibi arama işleminin etkinliği ağacın yüksekliğine bağlıdır. İkili arama ağaçları dengeli tutulabilirse, bir anahtar değerini aramada oldukça hızlıdırlar. Böyle olduğunda n elemanlı bir ağaç en fazla log₂n düzeyden oluşur. Bir değerin bulunması veya ağaçta olmadığının belirlenmesi için en fazla log₂n karşılaştırma yapılır. Örnek olarak 1000 elemanlı bir ikili arama ağacında bir elemanın bulunabilmesi için en fazla 10 karşılaştırma yapmak gerekecektir (2¹⁰=1024 > 1000). Bağlı listelerde ise bulunacak elemanın değerine göre (eleman sonda ise) 1000 karşılaştırma yapmak gerekebilir. 

Düğüm sayısı n olan Complete Binary Tree'de derinliği hesaplayabiliriz.

n = 2⁰ + 2¹ + 2² +... + 2^d = 2^d+1-1 => n+1 = 2^d+1 => d = log₂(n+1) - 1'dir.

15 düğümlü bir ağaçta d = log₂(15+1) - 1 = 4-1 = 3'tür.

İkili ağaçlardaki dolaşma işlemlerinin tümü ikili arama ağaçlarında da kullanılır. İkili arama ağaçları üzerinde inorder dolaşıldığında tüm elemanlar küçükten büyüğe sıralı bir şekilde karşımıza gelecektir.

İkili arama ağaçları, tekrarları önlemek açısından da oldukça yararlıdırlar. Ağaç oluşturulurken tekrar eden bir eleman eklenmek istendiğinde, kökten itibaren sola git, sağa git kararları ile o değerin olduğu yere hızlıca ulaşılacak ve ağaçta (veriler içinde) o değerin zaten olduğu anlaşılacaktır. Bu şekilde tekrar eden verilerin olması engellenir.  

Bunlar dışında ikili arama ağacından düğüm silme, ikili arama ağacını iki boyutlu ağaç biçiminde ekrana çizdirme, ağacı düzey sırasında dolaşma (düzey düzey soldan sağa) gibi algoritmalar da yazılabilir. Ayrıca ağaç düzeyini bulma, ağaca string de dahil birçok bilgi ekleme gibi işlemler de yapılabilir.

Bağlı liste veri yapısında ekleme, silme ve arama  işlemleri listedeki eleman sayısı n olmak üzere O(n)  kadar zaman almaktadır. İkili ağaç veri yapısı ise h  ağacın derinliğini göstermek üzere bu işlemlerin O(h)  kadar zamanda yapılmasını sağlar.  Dengeli bir ikili ağaçta sağ ve sol alt ağaçların derinlikleri farkı en fazla birdir. Eğer elimizdeki n tane elemanı dengeli bir ikili ağaca yerleştirirsek, bu ağaçtaki elemanlara ulaşma, ekleme ve silme işlemleri O(log n) kadar zaman alır.

Read More

Sıralama Algoritmaları /Selection Sort

Bilgisayar ortamında verilerin sıralı olması birçok işi kolaylaştırır. Arama , ekleme ,bölme vs. durumlarında verilerin sıralı olması ile olmaması arasında çok büyük performans farkı olabilir.
Birçok algoritma (örneğin binary search) sıralı veriler üzerinde çallışır.
Kullanıcı için de verilerin sıralı olması büyük kolaylık sağlar.
Verilerin sıralanması için birçok algoritma geliştirilmiştir.
 
Selection Sort , Bubble sort , İnsertion sort ,shell sort , Merge sort , Heap sort , Quick sort, Bucket sort , Radix sort, Distribution sort, Shuffle sort , Örnek sıralma algoritmalarıdır.
Sıralanacak verinin boyutu,yazılacak kod maliyeti , sistem kaynakları,
kullanıcı tercihi vb.durumlara göre herhangi biri tercih edilebilir.



Selection Sort

Sayı dizisini kullanacak olursak, algoritma ilk adımda tüm diziyi dolaşacak , en küçük elamanı bulup ilk sıraya yazacak. Sonra dizinin kalan kısmında aynı işi yeniden yapacak.Kalan kısmı tarayıp en küçük elemanı bulup,ikinci sıraya yazacak.Bu şekilde son elemana kadar gidip en küçükten büyüğe doğru dizimiz sıralanmış olacak.
 
__________________
__________________
Algoritma Mantığı

12,11,28,3,5,47

Dongünün 1.Adımı
i=0 k=i=0 s=a[0]=12

j=1 a[j]>s ? a[1]>12 False
j=2 a[j]>s ? a[2]>12 True

    s=a[2]=28 k=2

j=3 a[j]>s ? a[3]>28 False
j=4 a[j]>s ? a[4]>28 False
j=5 a[j]>s ? a[5]>28 True

    s=a[5]=47 k=5

s=a[k]=47
a[k]=a[i]=12
a[i]=s=47

47,11,28,3,5,12

i=1 k=i=1 s=[1]=11


j=2 a[j]>s ? a[2]>11  True


j=2 a[j]>s ? a[2]>11 True
s=a[2]=28
j=3 a[j]>s ? a[3]>28 False
j=4 a[j]>s ? a[4]>28 False
j=5 a[j]>s ? a[5]>28 False

    s=a[k]=28 a[k]=a[i]=11
a[i]=s=28

47,28,11,3,5,12
i=2
47,28,11,3,5,11
i=3
47,28,12,11,5,3
i=4
47,28,12,11,5,3
_________________
_________________
Selection Sort
#include <stdio.h>

int main(){
int i,j,k,l,n=6,s;
int a[6]={11,12,28,3,5,47};
for(i=0;i<n-1;i++){
k=i; s=a[i];
for(j=i+1;j<n;j++)
   if(a[j]>s)
     { s=a[j]; k=j; }
     s=a[k];
     a[k]=a[i];
     a[i]=s;
}
     for(i=0;i<n;i++)
   
     printf("Dizinin %d elemani %d dir\n",i+1,a[i]) ;


   
}


________________
________________
Aşamalarını görerek Selection sort

#include <stdio.h>

int main(){
int i,j,k,l,n=6,s;
int a[6]={11,12,28,3,5,47};
for(i=0;i<n-1;i++){
k=i; s=a[i];
for(j=i+1;j<n;j++)

   if(a[j]>s)
     { s=a[j]; k=j; }
     s=a[k];
     a[k]=a[i];
     a[i]=s;
   
      printf("Algoritmanin %d. adiminda dizi elemanlar asagidaki gibidir.\n",i+1) ;
      for(l=0;l<n;l++)
   
     printf("Dizinin %d. adımında elemani %d dir\n",l,a[l]) ;
}


}
__________________

__________________

Read More

Çok Boyutlu Diziler 2

Çok Boyutlu Diziler

Çok boyutlu bir diziyi tanımlarken,eleman değerlerini atamak mümkündür.
int ablo[3][4]={8,16,9,52,3,15,27,6,14,25,2,10};
Diziyi tanımlarken , yukarıdaki gibi bir ilk değer atama yaparsanız,elemanların değeri aşağıdaki gibi olur:

Satır 0 : 8 16 9 52

satır 1 : 3 15 27 6

satır 2 : 14 25 2 10

Daha iyi anlamak için şöylede yazılabilir

int ablo[3][4]={{8,16,9,52},{3,15,27,6},{14,25,2,10}};

Bir Matrisin Transpozesini Bulma

Bir  A matrisinin aynı numaralı satırlarıyle sütunlarının yer değiştirmesiyle elde edilen matristir.
A üssü t şeklinde gösterilir.


    a11 a12 a13                   a11 a21 a31
 A =a21 a22 a23                A= a12 a22 a32
    a31 a32 a33                   a13 a23 a33

Örnek Algoritme Mantığı
1 2 3
4 5 6
7 8 9
x=0
1.adım i=0 j=1
tmp=a[0,1]
a[0,1]=a[1,0]=4
a[1,0]=tmp=2
Meydana Gelen :
1 4 3
2 5 6
7 8 9
2.adım i=0 j=2
tmp=a[0,2]=3
a[0,2]=a[2,0]=7
a[2,0]=tmp=3
Meydana Gelen :
1 4 7
2 5 6
3 8 9
x=1
3.adım i=1 j=2
tmp=a[1,2]=6
a[1,2]=a[2,1]=8
a[2,0]=tmp=6
Meydana Gelen :
1 4 7
2 5 8
3 6 9
______________________

Program

--------------------
#include <stdio.h>
int main(){
int a[3][3]={{1,2,3},{4,5,6},{7,8,9}};
int i,j,x,tmp,n=3,m=3;
x=0;
for(i=0;i<n;i++){

for(j=x+1;j<m;j++){
tmp=a[i][j]; a[i][j]=a[j][i];
a[j][i]=tmp; printf("a dizisinin %d satiri %d sutunu %d\n",i,j,a[i][j]); }
x=x+1;}
for (i=0;i<n;i++)
   for(j=0;j<n;j++)
   printf("a dizisinin Devrik Versiyonunu %d satiri %d sutunu %d\n",i,j,a[i][j]);
}
______________________

Read More

İki sayı arasındaki Asal sayıların adedini veren C programı

#include <stdio.h>

int main(){

int i,c,d,a,b,x,e=0,sayac=1;
printf("ilk sayiyi girin");
scanf("%d",&a);
printf("ikinci sayiyi girin ");
 scanf("%d",&b);
for(i=a;i<=b;i++) 
{ d=1;
for (c=2;c<i;c++) 
{
if (i%c==0)
{d=0;}
}

if (d==1) { e=e+1;
printf(" %d",i);

}
}
printf("\n asal sayi adedi %d dir",e);
return 0;
}

Read More

ÇOK BOYUTLU DİZİLER 1

----------ÇOK BOYUTLU DİZİLER-------------------
Tek boyutlu diziler yanında istenilen boyutlardaki diziler kullanılabilir.Örneğin 3x4
bir matris için iki boyutlu bir dizi kullanılır.Ya da üç boyutlu Öklid uzayındaki x,y,z
noktalarını saklamak için 3 boyutlu bir diziyi tercih edilir.Örneğin
5 kişilik bir öğrenci grubu için
8 adet test uygulanırsa bunların sonuçlarını saklanması için
 2 boyutlu bir dizi kullanılması gereklidir.

----------------------ÇOKLU DİZİLİ PROGRAM--------------------------
BU KOD YENİDEN DÜZENLENDİ
#include <stdio.h>

int main(){
int ogrenci_tablosu[2][3];
int i,j;
for(i=0;i<2;i++){
 for(j=0;j<3;j++){
  printf("%d no.lu ogrencinin",(i+1));
  printf("%dno.lu sinavi>",(j+1));
  scanf("%d",&ogrenci_tablosu[i][j]);

 }
}
for(i=0;i<2;i++){
 for(j=0;j<3;j++){

  printf("%d no.lu ogrencinin %dno.lu sinavi>%d \n",i+1,j+1,ogrenci_tablosu[i][j]);
}
}
return 0;
}

--------------------------------------------------------------------

ÜÇ BOYUTLU DİZİ ÖRNEĞI

Read More

Linear / Sequential VE Binary Search (Doğrusal ve İkili Arama algoritması)

Linear / Sequential Search (Doğrusal Arama)

Doğrusal arama algoritması , klasik bir arama metodudur.

Sıklıkla kullanılır.Algoritma N boyutlu 

bir dizide ,istenilen eleman dizide bulunana kadar arama yapar,

yani eğer istenilen eleman ilk elemansa 

sadece bir kıyaslama yeterli olacaktır,eğer ikinci elemansa iki kıyaslama gerekecektir, 

genel olarak istenilen eleman dizideki k ıncı eleman olduğunu düşünürsek k kıyaslama gerekecektir

---------------------------------------------

------------Kendi yaptığım kontrol Programi---------------

#include <stdio.h>

int main(void){

int i,n,c,j,g,a;

    printf("\nDizinin bgenisligini giriniz:");

    scanf("%d",&n);

    int a[n];

    for (i=0;i<n;i++){

    printf("Dizinin %d elemanini giriniz",i+1);

    scanf("%d",&a[i]); }

    printf("eleman giriniz");

    scanf("%d",&c);

    printf("Aradiginiz sayi %d",c);

    for(i=0;i<=n;i++){

   

    if(c==a[i])

    printf("\nEleman sirasi %d",i+1);

  

}

      

    

   

    }

-------------------------------------------------

HOCANIN PROGRAMI

#include <stdio.h>

int main(void){

int i,aranan,sonuc=0,n;

printf("Dizinin boyutu: ");

scanf("%d",&n);

int a[n];

for(i=0;i<n;i++)

{

printf("dizinin %d elemani: ",i+1);

scanf("%d",&a[i]);

}

    printf("aranilan eleman giriniz");

    scanf("%d",&aranan);

    for(i=0;i<10;i++)

if(a[i]==aranan){

printf("aranilan eleman yeri %d dir",i+1);

sonuc=1;

break;}

   

  if(sonuc==0) printf("aranilan eleman yok");

  getch();

}

---------Binary Search (Mid Search)---------------

Sıralı bir dizide aranılan elemanın olup olmadığını bulur.

Diziyi ikiye bölerek diziyi sağına veya soluna doğru ilerlemeyi esas alır.

      

--------------------BİNARY SEARCH İLE KÜMEDE SAYI ARAMA------------------

#include <stdio.h>

int main(){

int ib,is,ic,i,aranan,n;

printf("Dizinin boyutu:");

scanf("%d",&n);

int a[n];

for(i=0;i<n;i++)

{

printf("Dizinin %d elemani :",i+1);

scanf("%d",&a[i]);}

printf("Aranilan eleman:");

scanf("%d",&aranan);

ib = 0; is=n-1; ic=(ib+is)/2;

while(ib<is) if(aranan==a[ic]) ib=is;

else if(aranan>a[ic]) {ib=ic+1;ic=(ib+is)/2;}

else {is=ic-1; ic=(ib+is)/2;}

if(aranan==a[ic]) printf("Aranilan eleman bulundu. Yeri %d dir",ic+1);

else printf("Aranan eleman bulunamadi");

}

------------------------------------------------

Read More