Veri Yapıları ve Algoritmalar: Giriş

Veri Yapısı ve Algoritmanın Farkı Nedir? | Ölçeklenebilirlik | Asimptotik Analiz | Böl ve Yönet Algoritması

Resim: Süleyman Demirel Üniversitesi (sdu.edu.tr)

Algoritma ve Veri Yapısı

1. Algoritma Nedir?

Algoritma, Harezmli Muhammed (Ebû Ca’fer Muhammed bin Mûsâ el-Hârizmî) tarafından ilk temelleri ortaya atılmıştır. Anlamı: Herhangi bir meseleyi sistematik şekilde adım adım çözmek için geliştirilip tâkip edilen usûl veya usûllerin bütünü, bir semboller cümlesine dayanan hesap metotları. (Kubbealtı Lügati)

2. Algoritma Nasıl Olmalı?

Etkili bir algoritmanın yazabilmesi için aşağıdaki kriterler göz önünde bulundurulmalıdır;

1. Girdinin nasıl bir çıktı üretmesi gerektiği tanımlanmalıdır.
2. Algoritmanın sürecini adım adım ve apaçık tanımlanmalıdır.
3. Algoritmanın tanımında, bilgisayar kodu yer almamalıdır.
4. Tüm programlama dillerinde uygulanabilir olmalıdır.

3. Algoritma ile Veri Yapısı Arasındaki Fark Nedir?

Programlama, iki temel unsurdan oluşur. Birincisi veri yapısı (data structure), ikincisi algoritma (algorithm). Veri yapıları verinin nasıl depolanacağı ile ilgili iken algoritma bu verilerin işlenmesi ile ilgilidir, bir süreç planlamasıdır. Şayet veriyi tahıl olarak düşünürsek: Veri yapısı, ambar (tahılı depolama süreci); algoritma, fabrikadır (tahılı işleme/planlama süreci).

Ölçeklenebilirlik (Scalability)

Programlamada en değerli iki kaynak, zaman ve bellektir.

Zaman için bir örnek verelim. Misal, 1’den 100’e kadar olan ardışık sayıların toplamını bulmak istiyorsunuz. Önünüze bir kâğıt aldınız ve tek tek sayıları topluyorsunuz. Her bir işlemi 1 saniyede yaptığınızı varsayarsak bu işlem, 99 saniye sürecektir. Bir de bu işlemi, formül üzerinden gerçekleştirdiğinizi düşünün (n*(n+1)/2). Bu formül ile işlem 3 saniye sürecektir (Yine her işlemin 1 saniye sürdüğünü varsayalım). Yaptığımız iki işlemi karşılaştırırsak 1. işlemde 2. işleme göre tam 32 kat zaman (96 saniye) kaybınız olacaktır.

Şimdi önümüzde 1’den 1.000.000’a kadar ardışık sayı olsun. 1. tip işlem 999.999 saniye sürecek iken 2. tip işlem 3 saniye sürecektir. Şimdiki zaman farkımız ise 333.332 kat (999.996 saniye) olacaktır. Bu algoritmanın performansıdır.

Bu misal, Ölçeklenebilirlik (Scalability) tanımına örnektir. Ölçeklenebilirlik, bir nevi işlem sayısını tahmin edebilme kabiliyetidir. 1. tip işleme Doğrusal Ölçeklenebilirlik Algoritması (Linearly Scalable Algorithm) denir iken 2. tip işleme Sabit Zaman Algoritması (Constant-Time Algorithm) diyoruz. Sabit Zaman Algoritması, kaç işlem yapılabileceğini daha iyi tahmin edebildiğimiz için daha ölçeklenebilirdir.

Asimptotik Analiz (Asymptotic Analysis)

Algoritmanın verimliliği, Asimptotik Belirtkeler (Notasyon) yardımıyla ölçülür. Girdi boyutu değiştikçe performansta değişir. Bunu da incelemek için Asimptotik Analizi kullanıyoruz. Bu analiz, girdi ile performansın değişimini incelememizi sağlar.

Asimptotik belirtke, çalışma süresini bilmemizi sağlar. Diyelim ki 1’den 10’a kadar ardışık sıralanmış sayı dizisinde 1 rakamını bulmak isteyelim. Bu dizide 1, en baştaki sayıdır ve ilk adımda bulmuş oluruz. Benzer şekilde 10’dan 1’e kadar ardışık sıralanmış bir sayı dizisinde 1 rakamını bulalım. O zaman 1 rakamını bulabilmemiz için 10 hamle yapmamız gerekli. Başka bir deyişle 10 kat daha fazla zaman kaybı olur. İşte buradaki ilk durum en iyi durumdur. İkinci durum ise en kötü durumdur. Bu gibi durumları; iyi, kötü, ortalama durum olarak 3 belirtke/gösterim (notasyon) ile gösteriyoruz.

1. Big-O Belirtkesi — O(f(n)): En kötü durum
2. Omega Belirtkesi— Ω(f(n)): En iyi durum
3. Teta Belirtkesi— Θ(f(n)): Ortalama durum

Böl ve Yönet Algoritması (Divide and Conquer Algorithm)

Böl ve Yönet Algoritmasını kullanmak için özyineleme (recursion) işlemi kullanmalıyız.

1. Böl: Büyük problemi küçük problemlere dönüştür.
2. Yönet: Küçük problemleri özyineleme yöntemi ile çöz. Şayet özyinelemeli ile çözülmesi doğrudan çözüme göre performansı düşük (daha maliyetli) ise doğrudan çözüm yap.
3. Birleştir: Küçük problemlerin çözümlerini birleştir ve büyük problemi çözüme kavuştur.

Sonuç olarak algoritma bilmek, yapacağımız programların verimli olmasını sağlar. Önceden sezebilme kabiliyetimizi geliştirir. Kısacası algoritma programımızın beynidir (bedeni işletir), veri yapısı kalbidir (beden için gerekli bileşenleri gerekli yerlere gönderir [bellek]).

Hayalim için çıktığım bu yolculukta, yazımı alkışlayarak bana destek olabilir misin?

Medium bizlere, her gönderi için 50 alkışa (clapping) kadar izin veriyor. Yazarlara destek olmak için beğendiğiniz kadar alkış atabilirsiniz.