Veri Yapıları - Algoritma Temelleri

Algoritma, istenen çıktıyı elde etmek için belirli bir sırayla yürütülecek bir dizi talimat tanımlayan adım adım bir prosedürdür. Algoritmalar genellikle temel dillerden bağımsız olarak oluşturulur, yani bir algoritma birden fazla programlama dilinde uygulanabilir.

Veri yapısı bakış açısından, aşağıda bazı önemli algoritma kategorileri verilmiştir:

Search - Bir veri yapısındaki bir öğeyi aramak için algoritma.
Sort - Öğeleri belirli bir sırayla sıralamak için algoritma.
Insert - Bir veri yapısına öğe eklemek için algoritma.
Update - Bir veri yapısındaki mevcut bir öğeyi güncelleme algoritması.
Delete - Bir veri yapısından mevcut bir öğeyi silmek için algoritma.

Bir Algoritmanın Özellikleri

Tüm prosedürler bir algoritma olarak adlandırılamaz. Bir algoritma aşağıdaki özelliklere sahip olmalıdır -

Unambiguous- Algoritma açık ve net olmalıdır. Adımlarının (veya aşamalarının) her biri ve girdileri / çıktıları açık olmalı ve yalnızca bir anlama yol açmalıdır.
Input - Bir algoritma, 0 veya daha fazla iyi tanımlanmış girdiye sahip olmalıdır.
Output - Bir algoritma 1 veya daha fazla iyi tanımlanmış çıktıya sahip olmalı ve istenen çıktıyla eşleşmelidir.
Finiteness - Algoritmalar, sınırlı sayıda adımdan sonra sona ermelidir.
Feasibility - Mevcut kaynaklarla mümkün olmalıdır.
Independent - Bir algoritma, herhangi bir programlama kodundan bağımsız olması gereken adım adım talimatlara sahip olmalıdır.

Algoritma Nasıl Yazılır?

Algoritma yazmak için iyi tanımlanmış standartlar yoktur. Aksine, sorunludur ve kaynağa bağlıdır. Algoritmalar asla belirli bir programlama kodunu desteklemek için yazılmaz.

Tüm programlama dillerinin döngüler (do, for, while), akış kontrolü (if-else) vb. Gibi temel kod yapılarını paylaştığını bildiğimiz için. Bu yaygın yapılar bir algoritma yazmak için kullanılabilir.

Algoritmaları adım adım yazıyoruz, ancak durum her zaman böyle değil. Algoritma yazma bir süreçtir ve problem alanı iyi tanımlandıktan sonra yürütülür. Yani çözüm tasarladığımız problem alanını bilmeliyiz.

Misal

Bir örnek kullanarak algoritma yazmayı öğrenmeye çalışalım.

Problem - İki sayı eklemek ve sonucu görüntülemek için bir algoritma tasarlayın.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Algoritmalar, programcılara programı nasıl kodlayacaklarını söyler. Alternatif olarak, algoritma şu şekilde yazılabilir:

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Algoritmaların tasarımında ve analizinde genellikle ikinci yöntem bir algoritmayı tanımlamak için kullanılır. Analistin, tüm istenmeyen tanımları göz ardı ederek algoritmayı analiz etmesini kolaylaştırır. Hangi işlemlerin kullanıldığını ve sürecin nasıl aktığını gözlemleyebilir.

yazı step numbers, İsteğe bağlı.

Belirli bir problemin çözümünü elde etmek için bir algoritma tasarlarız. Bir problem birden fazla yolla çözülebilir.

Dolayısıyla, belirli bir problem için birçok çözüm algoritması türetilebilir. Bir sonraki adım, önerilen çözüm algoritmalarını analiz etmek ve en uygun çözümü uygulamaktır.

Algoritma Analizi

Bir algoritmanın etkinliği, uygulama öncesinde ve sonrasında olmak üzere iki farklı aşamada analiz edilebilir. Aşağıdakilerdir -

A Priori Analysis- Bu, bir algoritmanın teorik analizidir. Bir algoritmanın verimliliği, diğer tüm faktörlerin, örneğin işlemci hızının sabit olduğu ve uygulama üzerinde hiçbir etkisinin olmadığı varsayılarak ölçülür.
A Posterior Analysis- Bu, bir algoritmanın deneysel bir analizidir. Seçilen algoritma, programlama dili kullanılarak uygulanır. Bu daha sonra hedef bilgisayar makinesinde yürütülür. Bu analizde, çalışma süresi ve gerekli alan gibi gerçek istatistikler toplanır.

Bir priori algoritma analizi öğreneceğiz . Algoritma analizi, ilgili çeşitli işlemlerin yürütülmesi veya çalıştırılma süresiyle ilgilenir. Bir işlemin çalışma süresi, işlem başına yürütülen bilgisayar talimatlarının sayısı olarak tanımlanabilir.

Algoritma Karmaşıklığı

Varsayalım X bir algoritmadır ve n Girdi verilerinin boyutu, X algoritması tarafından kullanılan zaman ve alan, X'in verimliliğini belirleyen iki ana faktördür.

Time Factor - Zaman, sıralama algoritmasındaki karşılaştırmalar gibi anahtar işlemlerin sayısı sayılarak ölçülür.
Space Factor - Alan, algoritmanın gerektirdiği maksimum bellek alanı sayılarak ölçülür.

Bir algoritmanın karmaşıklığı f(n) algoritmanın ihtiyaç duyduğu çalışma süresini ve / veya depolama alanını verir. n giriş verilerinin boyutu olarak.

Uzay Karmaşıklığı

Bir algoritmanın uzay karmaşıklığı, algoritmanın yaşam döngüsü boyunca ihtiyaç duyduğu bellek alanı miktarını temsil eder. Bir algoritmanın gerektirdiği alan, aşağıdaki iki bileşenin toplamına eşittir -

Sorunun boyutundan bağımsız olan, belirli verileri ve değişkenleri depolamak için gereken alan olan sabit bir parça. Örneğin, kullanılan basit değişkenler ve sabitler, program boyutu vb.
Değişken parça, boyutu problemin boyutuna bağlı olan değişkenler tarafından ihtiyaç duyulan bir alandır. Örneğin, dinamik bellek ayırma, özyineleme yığın alanı vb.

Herhangi bir P algoritmasının uzay karmaşıklığı S (P), S (P) = C + SP (I) 'dir, burada C sabit kısımdır ve S (I), örnek karakteristiğine I bağlı olan algoritmanın değişken kısmıdır. kavramı açıklamaya çalışan basit bir örnektir -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Burada A, B ve C olmak üzere üç değişkenimiz ve bir sabitimiz var. Dolayısıyla S (P) = 1 + 3. Uzay artık verilen değişkenlerin veri türlerine ve sabit türlere bağlıdır ve buna göre çarpılacaktır.

Zaman Karmaşıklığı

Bir algoritmanın zaman karmaşıklığı, algoritmanın tamamlanması için gereken süreyi temsil eder. Zaman gereksinimleri sayısal bir fonksiyon T (n) olarak tanımlanabilir, burada T (n) her adımın sabit zaman harcaması koşuluyla adım sayısı olarak ölçülebilir.

Örneğin, iki n-bit tamsayının eklenmesi, nadımlar. Sonuç olarak, toplam hesaplama süresi T (n) = c ∗ n'dir, burada c, iki bitin eklenmesi için geçen süredir. Burada, girdi boyutu arttıkça T (n) 'nin doğrusal olarak büyüdüğünü gözlemliyoruz.