Giriş
Big O işlenen eleman sayısı arttıkça, gerekli sürenin de ne kadar artacağını gösterir. Yani girdinin niceliği arttıkça algoritmanın ne kadar daha çok vakit aldığını anlamak için kullanırız. Açıklaması şöyle.
Az sayıdaki eleman için Big O'yu tartışmak anlamsızdır. Örneğin çok kısa bir mesafe, yürüyerek, bisikletle veya arabayla gidilebilir ve gereken süre belki de hepsi için o kadar az fark eder ki , O(1) ya da O(n) olmasının bir önemi kalmaz!
Big O işlenen eleman sayısı arttıkça, gerekli sürenin de ne kadar artacağını gösterir. Yani girdinin niceliği arttıkça algoritmanın ne kadar daha çok vakit aldığını anlamak için kullanırız. Açıklaması şöyle.
Big-O Notation describes scalability
At its core, Big-O Notation is not a description of how long an algorithm takes to run. Nor is it a description of how many steps, lines of code, or comparisons an algorithm makes. It is most useful when used to describe how an algorithm scales with the number of inputs.
Big O belirtmek için söylenen cümleler şöyledir
The two phrases- The running time is O(n2)and- The running time is at most O(n2)mean the same thing.
Big O Sonucu
Bu değer her zaman artı bir değerdir. Açıklaması şöyle
running times of algorithms are positive integers
Benchmarking
Açıklaması şöyle. Yani sadece Big O'yu bulmak yeterli değil. Hala benchmarking gerekli.
Reading between the lines, I think you may be misunderstanding Big O analysis as being a replacement for benchmarking. It's not. An engineer still needs to benchmark their code if they want to know how fast it is. And indeed in the real world, an O(n) algorithm might be slower than an O(n2) algorithm on real-world data sets.
Asymptotic Kelimesi
Bazen Big O için yapılan açıklamalarda asymptotic kelimesi kullanılıyor. Asymptotic için açıklama şöyle.Az Sayıdaki Eleman İçin Big OWhen we look at input sizes large enough to make only the order of growth of the running time relevant, we are studying the asymptotic efficiency of algorithms.That is, we are concerned with how the running time of an algorithm increases with he size of the input in the limit, as the size of the input increases without bound. Usually, an algorithm that is asymptotically more efficient will be the best choice for all but very small inputs.
Az sayıdaki eleman için Big O'yu tartışmak anlamsızdır. Örneğin çok kısa bir mesafe, yürüyerek, bisikletle veya arabayla gidilebilir ve gereken süre belki de hepsi için o kadar az fark eder ki , O(1) ya da O(n) olmasının bir önemi kalmaz!
Big O'dan Söz Edilemeyen Durumlar
Sadece "Hello World" yazan bir programın, girdisi yani işlenen eleman sayısı olmadığı için Big O gösteriminden söz edilemez.
Big O gösterimi yanında Teta ve Omega gösterimleri de var. Big O ve diğer gösterimler P (Polynomial) algoritmalar için kullanılır. Big O algoritmanın sadece üst sınırını belirtir yani upper bound'u belirtir.
Omega Gösterimi Nedir
Omega alt sınırı yani lower bound'u belirtir. Sembolü şöyledir. At nalı gibidir.
Sadece "Hello World" yazan bir programın, girdisi yani işlenen eleman sayısı olmadığı için Big O gösteriminden söz edilemez.
Big O ve Diğer GösterimlerBig O notation exists to describe a relationship between the size of the input of a function and the number of operations that need to be performed to compute the result for that input.
Your operation has no input that the output can be related to, so using Big O notation is nonsensical. The time that the operation takes is independent of the inputs of the operation (which is...none). Since there is no relationship between the input and the number of operations performed, you can't use Big O to describe that non-existent relationship
Big O gösterimi yanında Teta ve Omega gösterimleri de var. Big O ve diğer gösterimler P (Polynomial) algoritmalar için kullanılır. Big O algoritmanın sadece üst sınırını belirtir yani upper bound'u belirtir.
Omega Gösterimi Nedir
Omega alt sınırı yani lower bound'u belirtir. Sembolü şöyledir. At nalı gibidir.
Ω(⋅) is a lower boundTeta Gösterimi Nedir
Teta algoritmanın alt ve üst sınırını belirtir.
Bir algoritma özel bir iş/durum için en iyi sonucu veriyorsa Asymptotically Optimal denir.
Big O Karşılaştırması
Aşağıda bazı algoritmaların karşılaştırmaları var.
Big O ve Veri Yapıları
Veri yapılarının Big O değerleri şöyle.
Big O ve Sabitler - Scalar (Sayıl) Value
Big O sabitleri dikkate almaz. Bu yüzden f(n) = n ve g(n) = 10n her zaman O(n) kabul edilirler.
Logaritma olsaydı da sabitler fark yaratmazdı. Matematiksel olarak aynı kabul ediliyorlar ve bu durum algoritmaları karşılaştırmayı kolaylaştırıyor.
Ancak pratik kullanımda an^2 + bn + c gibi bir formülde a, b ve c'nin önemsiz kabul edilmesi doğru olmayabilir. Çünkü 2n^2 ve n^2 şeklinde çalışan iki algoritma arasından n^2'yi tercih etmek gerekir. Yani pratikte sabitler önemli.
Big O ve Veri Yapıları Üzerindeki Farklı İşlemler
Veri yapısına ekleme, silme gibi işlemlerin genellikle maliyetleri farklı değerlerdir. Bu değerlerin en iyi, en kötü ve ortalama maliyetleri de vardır.
The Theta-notation asymptotically bounds a function from above and below. When we have only an asymptotic upper bound, we use O-notation.Sembolü şöyledir. O harfinin ortasında yatay bir çizgi var gibidir.
Θ(1)Asymptotically Optimal Nedir
Bir algoritma özel bir iş/durum için en iyi sonucu veriyorsa Asymptotically Optimal denir.
Big O Karşılaştırması
Aşağıda bazı algoritmaların karşılaştırmaları var.
Big O ve Veri Yapıları
Veri yapılarının Big O değerleri şöyle.
Big O ve Sabitler - Scalar (Sayıl) Value
Big O sabitleri dikkate almaz. Bu yüzden f(n) = n ve g(n) = 10n her zaman O(n) kabul edilirler.
Logaritma olsaydı da sabitler fark yaratmazdı. Matematiksel olarak aynı kabul ediliyorlar ve bu durum algoritmaları karşılaştırmayı kolaylaştırıyor.
Ancak pratik kullanımda an^2 + bn + c gibi bir formülde a, b ve c'nin önemsiz kabul edilmesi doğru olmayabilir. Çünkü 2n^2 ve n^2 şeklinde çalışan iki algoritma arasından n^2'yi tercih etmek gerekir. Yani pratikte sabitler önemli.
Big O ve Veri Yapıları Üzerindeki Farklı İşlemler
Veri yapısına ekleme, silme gibi işlemlerin genellikle maliyetleri farklı değerlerdir. Bu değerlerin en iyi, en kötü ve ortalama maliyetleri de vardır.
O(1) - Constant
O(1) - Constant yazısına taşıdım.
O(1) - Constant yazısına taşıdım.
O(log(n)) - Logaritmic
O(log(n) - Logaritmic yazısına taşıdım
O (n) - Linear
O(n) - Linear yazısına taşıdım.
O(log(n) - Logaritmic yazısına taşıdım
O (n) - Linear
O(n) - Linear yazısına taşıdım.
O (n log(k))
Burada k en büyük/küçük k tane elemanı temsil ediyor. Örneğin bir dizideki en büyük 100 elemanı bulmanın maliyeti bu olabilir. En büyük en küçük k tane eleman saklamak için priority queue kullanılır. O (n log(n)) algoritmalara göre maliyeti daha düşüktür.
O(n log(n)) - Quasi Linear
Quasi Linear ismi çok tuhaf.
log (n) n sayısının 2 tabanındaki logaritması anlamına geliyor. Yani n sayısının kaç defa 2'ye bölünebildiği demek. Genel olarak divide and conquer algoritmaları bu karmaşıklığa sahiptir.
Özel olaraksa Quicksort örnek verilebilir.
Aşağıdaki kod parçasında dıştaki döngü O(n) içteki döngü ise j*=2 yüzünden O(log n). O(n) * O(log n) ise = O (n log(n))
O(n2) - İkinci Dereceden Yani Quadratic
O(n^2) - Quadratic yazısına taşıdım
Burada k en büyük/küçük k tane elemanı temsil ediyor. Örneğin bir dizideki en büyük 100 elemanı bulmanın maliyeti bu olabilir. En büyük en küçük k tane eleman saklamak için priority queue kullanılır. O (n log(n)) algoritmalara göre maliyeti daha düşüktür.
O(n log(n)) - Quasi Linear
Quasi Linear ismi çok tuhaf.
log (n) n sayısının 2 tabanındaki logaritması anlamına geliyor. Yani n sayısının kaç defa 2'ye bölünebildiği demek. Genel olarak divide and conquer algoritmaları bu karmaşıklığa sahiptir.
Özel olaraksa Quicksort örnek verilebilir.
Aşağıdaki kod parçasında dıştaki döngü O(n) içteki döngü ise j*=2 yüzünden O(log n). O(n) * O(log n) ise = O (n log(n))
int sum = 0;
for(i = 1; i <= inputSize; i++){
for(j = i; j < inputSize; j *=2 ){
printf("The value of sum is %d\n",++sum);
}
}
O(n2) - İkinci Dereceden Yani Quadratic
O(n^2) - Quadratic yazısına taşıdım
O(n3) - Üçüncü Dereceden Yani Cubic
Matris çarpımı iç içe geçmiş üç döngü içerdiği için üçüncü derecedendir. Açıklamayı burada bulabilirsiniz.
O(n!)
Permütasyon hesaplamalarında bu değeri elde ediyoruz. O(n!) O(n^n)'den yine de daha iyidir. Recursive bir örnek için buraya bakabilirsiniz. Travelling Salesman (gidilmesi gereken noktaların hepsine sadece bir kez uğrayarak maliyeti en düşük şekilde tutarak başlangıca dönmeyi gerektiren problem) probleminin de permütasyon kullandığı için O(n!) olduğu yazılı.
Matris çarpımı iç içe geçmiş üç döngü içerdiği için üçüncü derecedendir. Açıklamayı burada bulabilirsiniz.
O(n!)
Permütasyon hesaplamalarında bu değeri elde ediyoruz. O(n!) O(n^n)'den yine de daha iyidir. Recursive bir örnek için buraya bakabilirsiniz. Travelling Salesman (gidilmesi gereken noktaların hepsine sadece bir kez uğrayarak maliyeti en düşük şekilde tutarak başlangıca dönmeyi gerektiren problem) probleminin de permütasyon kullandığı için O(n!) olduğu yazılı.
Big O ve İç içe Döngüler
İç içe döngü kullanan aşağıdaki sorunun cevabı burada. Aşağıdaki sorunun cevabı 2n-1
Big O ve Auxilary Storage
Algoritmalar incelenirken sadece time complexity özelliklerine değil aynı zamanda ne kadar hafıza kullandıklarına da bakılabilir. Örneğin Sorting algoritm sayfasında Memory başlığı altında algoritmanın ne kadar hafızaya ihtiyaç duydukları da incelenmiş.
Quicksort gibi bir algoritma özyinelemeli (recursive) olarak çalışıyorsa ,log(n) stack büyüklüğüne ihtiyaç duyar. Merge sort ise O(n) heap büyüklüğüne ihtiyaç duyabilir.
İç içe döngü kullanan aşağıdaki sorunun cevabı burada. Aşağıdaki sorunun cevabı 2n-1
Algoritmalar incelenirken sadece time complexity özelliklerine değil aynı zamanda ne kadar hafıza kullandıklarına da bakılabilir. Örneğin Sorting algoritm sayfasında Memory başlığı altında algoritmanın ne kadar hafızaya ihtiyaç duydukları da incelenmiş.
Quicksort gibi bir algoritma özyinelemeli (recursive) olarak çalışıyorsa ,log(n) stack büyüklüğüne ihtiyaç duyar. Merge sort ise O(n) heap büyüklüğüne ihtiyaç duyabilir.
Hiç yorum yok:
Yorum Gönder