Video: Algoritma Ve Programlama Mantığı & Yeni Başlayanlar 2024
Matematikteki bir işlev, bazı girdileri bir yanıtla eşleştirmenin basit bir yoludur. Farklı bir şekilde ifade edilen bir işlevi, girdinizi bir cevap haline getiren (haritalandıran) bir dönüşümdür (matematik işlemlerine dayalıdır).
Bazı girdi değerleri (genellikle x veya n harfleriyle gösterilir) için, fonksiyonu tanımlayan matematiğe karşılık gelen bir cevabınız vardır. Örneğin, f (n) = 2 n gibi bir işlev, girişiniz n, sayı olduğunda n sayısının 2 ile çarpımıdır.
Girişin boyutunu kullanmak, bunun zaman açısından kritik bir yaş olduğu ve insanların hayatlarının gittikçe artan bir miktarda veriyle sıkıştığı göz önüne alındığında mantıklı geliyor. Her şeyi matematiksel bir işlev yapmak biraz daha sezgisel, ancak bir algoritmanın aldığı verinin miktarıyla çözümünü nasıl ilişkilendirdiğini açıklayan bir işlev, belirli donanım veya yazılım desteği olmadan analiz edebileceğiniz bir şeydir. Sorununuzun büyüklüğü göz önüne alındığında, diğer çözümlerle karşılaştırmak da kolaydır. Algoritmaların analizi gerçekten zihin bulan bir kavramdır çünkü karmaşık bir dizi basamağı bir matematik formüle indirgemektedir.
Dahası, çoğu zaman, algoritmaların bir analizi bile fonksiyonu tam olarak tanımlamakla ilgilenmiyor. Gerçekten yapmak istediğiniz şey, bir hedef işlevin başka bir işlevle karşılaştırılmasıdır. Bu karşılaştırma işlevleri, hedef algoritma ile karşılaştırıldığında zayıf performans sergileyen önerilen işlevler dizisinde görülür. Bu sayede, sayıları daha büyük veya daha az karmaşıklığa sahip fonksiyonlara eklemek zorunda kalmazsınız; Bunun yerine basit, premade ve iyi bilinen işlevleri ele alırsınız. Kaba gibi gelebilir, ancak daha etkili ve kesin bir performans ölçümü elde etmek yerine, algoritmaların performansını kategorilere sınıflandırmaya benzer.
Genelleştirilmiş işlevler kümesine Büyük O gösterimi denir ve sıklıkla bu küçük işlev kümesiyle karşılaşırsınız (parantez içine alınır ve başına bir O >) algoritmaların performansını göstermek için kullanılır. Şekilde bir algoritmanın analizi gösterilmektedir. Kartezyen koordinat sistemi, yatay (x koordinatı) girdinin boyutu ve ordinat (y koordinatı) olduğu RAM simülasyonuyla ölçülen işlevini temsil edebilir sonuçlanan işlem sayısı. Üç eğri temsil ettiğini görebilirsiniz. Girdi boyutu önemlidir. Bununla birlikte, kalite de önemlidir (örneğin, sorun siparişi verirken, neredeyse emredilen bir girdiyi sipariş etmek daha hızlıdır).Sonuç olarak analiz, en kötü durum, f 1 (n), ortalama bir vaka, f 2 (n) ve en iyi vaka, f 3 (n). Ortalama bir vaka size genel bir fikir verebilir, ancak gerçekten önem verdiğiniz şey en kötü durumdur, çünkü algoritmanız bir çözüm bulmaya çalışırken problemler ortaya çıkabilir. Big O işlevi, belli bir
n0
değerinden (büyük girdi kabul etmek için eşik değeri) sonra, her zaman aynı girdi verilen daha büyük sayıdaki operasyonlara en kötü durum fonksiyonu olan 'dan daha fazla sonuç verir > f1
. Böylece, Big O işlevi algoritmanınızı temsil eden iştahtan daha kötümser olur, böylece girdi kalitesi olursa olsun, işlerin bundan daha kötü olamayacağından emin olabilirsiniz.
En iyi, ortalama ve en kötü girdi durumunda bir algoritmanın karmaşıklığı.
Birçok olası işlev daha kötü sonuçlar doğurabilir ancak kullanabileceğiniz Big O gösterimi tarafından sunulan işlevlerin seçimi kısıtlıdır, çünkü amacı bir standart önererek karmaşıklık ölçümünü basitleştirmektir. Sonuç olarak, bu bölüm Big O notasyonunun bir parçası olan sadece birkaç fonksiyonu içermektedir. Aşağıdaki liste artan karmaşıklık derecesinde şunları açıklamaktadır:
Aynı anda, ne kadar çok girdi sağlamak olursa olsun. Sonunda, girilen verinin ne kadar uzun olursa olsun, sabit bir sayıdaki işlemdir. Bu karmaşıklık seviyesi uygulamada oldukça nadirdir.
- Logaritmik karmaşıklık O (log n): İşlemlerin sayısı girdiden daha yavaş büyür ve algoritmayı küçük girdilerle daha az verimli, daha büyük olanlarla daha verimli hale getirir. Bu sınıfın tipik bir algoritması ikili aramadır.
- Doğrusal karmaşıklık O (n): İşlemler girişle 1: 1 oranında büyür. Tipik bir algoritma, girişi bir kez taradığınızda ve onun her bir öğesine bir işlem uyguladığınızda tekrarlama işlemidir.
- Linearitmik karmaşıklık O (n log n): Karmaşıklık, logaritmik ve doğrusal karmaşıklık arasındaki bir karışımı ifade eder. Mergesort, Heapsort ve Quicksort gibi verileri sipariş etmek için kullanılan bazı akıllı algoritmalara özgüdür.
- İkinci dereceden karmaşıklık O (n 2
- ): İşlemler, girdi sayısının karesi kadar büyür. Başka yinelemelerde (bilgisayar biliminde iç içe geçmiş yinelemeler) tek bir iterasyona sahipseniz, ikinci derece karmaşıklığa sahipsinizdir. Örneğin, bir isim listesi var ve en benzer olanları bulmak için her ismi diğer tüm isimlerle karşılaştırıyorsunuz. Bazı daha az etkili sipariş algoritmaları böyle karmaşıklığı sunar: kabarcık sıralama, seçim sıralama ve ekleme sıralama. Bu karmaşıklık düzeyi, algoritmalarınızın bir çözüm bulmadan önce saatlerce hatta günler sürebilir anlamına gelir. Kübik karmaşıklık O (n 3
- ): İşlemler karesel karmaşıklığa göre daha hızlı büyür, çünkü şimdi birden çok iç içe geçmiş yinelemeye sahipsiniz. Bir algoritma bu karmaşıklık derecesine sahipse ve az miktarda veri (100, 000 öğe) işlemek zorunda kalırsanız, algoritma yıllarca çalışabilir.Girişin gücü olan bir dizi işlemi yaptığınızda, algoritmaya polinom zamanında çalışan 'a bakın. Üstel karmaşıklık O (2 n
- ): Algoritma, eklenen her yeni öğe için önceki işlemlerin iki katı sayı alır. Bir algoritma bu karmaşıklığa sahip olduğunda, küçük sorunlar bile sonsuza kadar sürebilir. Kapsamlı aramalar yapan birçok algoritmanın üstel karmaşıklığı vardır. Bununla birlikte, bu karmaşıklık seviyesi için klasik örnek Fibonacci sayılarının hesaplanmasıdır. Faktöriyel karmaşıklık O (n!): Elementler arasındaki olası kombinasyonların çokluğu nedeniyle gerçek karmaşık bir kabus. Düşünüyorsanız: Girişiniz 100 nesneyse ve bilgisayarınızdaki bir işlem 10 999 -6 -6999 saniyedir (günümüzde her bilgisayar için makul bir hız), yaklaşık 10
- 140 yılına ihtiyaç duyarsanız görevi başarıyla tamamlamak için (evrenin yaşının 10 14 yıl olduğu tahmin edilemez bir zaman süresi). Ünlü bir faktöryal karmaşıklık problemi, bir satış elemanının pek çok şehri ziyaret etmek ve başlangıç şehrine geri dönmek için en kısa güzergahı bulması gereken seyyar satıcı meselesidir.
