- 3 Tem 2016
- 500
- 0
Merhaba ben TTRTAHIR, formda DSA adına yeterli kaynak ve yazının bulunmadığını düşünüp Big-O notasyonunu açıklamak istedim, çok düzenli bir seri olabileceğini garanti edemem ancak eğer yeterli vaktim ve enerjim olursa daha fazla örnek, daha fazla konu yazmak istiyorum, şimdiden teşekkürler.
Big-O notasyonundan bahsetmeden önce bilmemiz gereken şeyler var: algoritmaları neden en iyi olasılık, en kötü olasılık diye farklı şekillerde bakıyoruz ve bunalara ne ad veriliyor.
Algoritmalarin asimptotik analizi nedir?
Asimptotik fonksiyonlarin limiti için kullanılan bir metottur, bu metotta f
gibi bir fonksiyonun n'in çok büyük değerleri için davranışlarını inceler. Çok büyük değerler olmasının sebebi de şudur ki: bazen bir algoritma kısa vadede size iyi bir sonuç sağlayabilirken uzun vadede sorunlar çıkartabilir.
Basit bir ornek vericek olursak Double, Triple Looplar sizin icin cozumu o anda sağlayabilir ama n icin sayi sonsuza yaklastiginda çok çok uzun süreler beklememiz gerekecektir. Kısaca özetleyecek olursak, asimptotik analiz sonsuza giden bir gözlemin özelliklerini belirtmek icin kullanilir diyebiliriz.
Big-O notasyonundan bahsetmeden önce bilmemiz gereken şeyler var: algoritmaları neden en iyi olasılık, en kötü olasılık diye farklı şekillerde bakıyoruz ve bunalara ne ad veriliyor.
Algoritmalarin asimptotik analizi nedir?
Asimptotik fonksiyonlarin limiti için kullanılan bir metottur, bu metotta f
gibi bir fonksiyonun n'in çok büyük değerleri için davranışlarını inceler. Çok büyük değerler olmasının sebebi de şudur ki: bazen bir algoritma kısa vadede size iyi bir sonuç sağlayabilirken uzun vadede sorunlar çıkartabilir. Basit bir ornek vericek olursak Double, Triple Looplar sizin icin cozumu o anda sağlayabilir ama n icin sayi sonsuza yaklastiginda çok çok uzun süreler beklememiz gerekecektir. Kısaca özetleyecek olursak, asimptotik analiz sonsuza giden bir gözlemin özelliklerini belirtmek icin kullanilir diyebiliriz.
Peki Big-O notasyonu nedir? Ne işe yarar?
Fonksiyonlarin asimptotik davranislarini ifade etmek icin kullanilir, daha açık ifade etmek gerekirse işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması demektir. Bilgisayar bilimlerinde algoritmalarin karmaşıklığını ölçmek için kullanılan bir yöntemdir.
Fonksiyonlarin asimptotik davranislarini ifade etmek icin kullanilir, daha açık ifade etmek gerekirse işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması demektir. Bilgisayar bilimlerinde algoritmalarin karmaşıklığını ölçmek için kullanılan bir yöntemdir.
İkiye ayrilir: sonsuz asimptotikler ve infinitesimal (sonsuz küçük) asimptotikler.
Sonsuz asimptotikler:
Algoritma başarı çözümlemesinde kullanır bu yöntem, bir nevi algortmanizin ne kadar başarılı olduğunu ölçer. Örneğin n boyutlu bir problemi çözmek için gerekli olan zaman (tüketilecek zaman, algoritma başıyla sonu arasındaki zaman) F = 4n² - 2n + 2 olarak bulunabilir. n'in büyümesine kıyasla n²'nin büyümesi çok daha hızlı olacağından dolayı sonsuzda n² ifadesinin yaninda n bir şey ifade etmez varsayılır ve algoritmanin big O notation'da karmaşıklığı F ∈ O(n²) şeklinde ifade edilir.
İnfinitesimal asimptotikler ise bir matematiksel işlev için geliştirilen yaklaşık işlevin hata terimini tarif etmek için kullanılır.
Algoritma başarı çözümlemesinde kullanır bu yöntem, bir nevi algortmanizin ne kadar başarılı olduğunu ölçer. Örneğin n boyutlu bir problemi çözmek için gerekli olan zaman (tüketilecek zaman, algoritma başıyla sonu arasındaki zaman) F
= 4n² - 2n + 2 olarak bulunabilir. n'in büyümesine kıyasla n²'nin büyümesi çok daha hızlı olacağından dolayı sonsuzda n² ifadesinin yaninda n bir şey ifade etmez varsayılır ve algoritmanin big O notation'da karmaşıklığı F ∈ O(n²) şeklinde ifade edilir.İnfinitesimal asimptotikler ise bir matematiksel işlev için geliştirilen yaklaşık işlevin hata terimini tarif etmek için kullanılır.
Sık rastlanan işlev dereceleri
yukardan aşağıya gittikçe karmaşıklık artar ve algoritma başarısı düşer.
Peki bu bizim gerçek hayatta ne işimize yarıyacak
Tablodaki bazi notasyonlari açıklayalım:
Peki bu bizim gerçek hayatta ne işimize yarıyacak
Tablodaki bazi notasyonlari açıklayalım:
O(1) Sabit Karmaşıklık:
Elinizde bulunan veri ne kadar büyük olursa olsun, çalıştırılma süresi her daim sabittir.
Kod:
int ilkElemaniYazdir(int* arr){
printf("Ilk eleman: %d\n",arr[0])
}Bir arrayın ilk değerini yazdırmak buna örnek olabilir.
O Doğrusal Karmaşıklık
Elimizdeki veri seti arttıkça, çalıştırılma süresinin doğru orantılı arttığı karmaşıklıktır.
Doğrusal KarmaşıklıkElimizdeki veri seti arttıkça, çalıştırılma süresinin doğru orantılı arttığı karmaşıklıktır.
Kod:
int ilkElemanlariYazdir(int* arr, int size){
for(int i = 0; i <= size ; i++ )
printf("%d.ci eleman: %d\n",i,arr[i]);
}Bir array ve array büyüklüğü verilir ve her elemanı yazılması istenirse, her biri için O(1) karmaşıklık söz konusudur.
O(n^2) Karesel Karmaşıklık
Input'un büyüklüğünün karesiyle doğru orantılıdır.
Double Loop'lar bunlara örnek verilebilir
Double Loop'lar bunlara örnek verilebilir
O(log n) Logaritmik Karmaşıklık
Genelde her seferinde problemi ikiye bölen algoritmalarda kullanılır. Örneğin bir sayı tahmin oyununu kazanmak için en iyi yöntem tam ortadaki sayıyı söylemek ve her seferinde ihtimalleri yarıya indirmektir, bu algoritma da logaritmik karmaşıklığa sahiptir.
Yine örnek olarak merge sort akıllara gelebilir.
Yine örnek olarak merge sort akıllara gelebilir.
O(c^n) Exponansiyel Karmaşıklık
Input n ise, output'u c^n olan algoritmalardır. Recursive örnek olarak verilebilir.
Kod:
int fibonacci(int num){
if (num <= 1) return num;
return fibonacci(num - 2) + fibonacci(num - 1);
}C = 2 için 2^n fibonaccinin karmaşıklığı olabilir.
Bir örnekle pekiştirelim:
Kod:
main() {
ios_base::sync_with_stdio(0); cin.tie(0);
auto solve = [](){
int n(0);cin>>n;
vi a(n);
string s;cin>>s;
for(int i(0), cur(n) ,j(0) ; i<n ; i=j+1 ){
for(j = i ; j<n-1 & s[j] == '<' ; j++);
for(int k(j) ; k>=i ; k--) a[k] = cur--;
}
for(int& it : a) cout << it << " "; cout << endl;
for(int i(0), cur(1), j ; i<n ; i=j+1){
for(j=i ; j<n-1 & s[j] == '>' ; j++);
for(int k(j) ; k>=i ; k--) a[k] = cur++;
}
for(int& it : a) cout << it << " "; cout << endl;
}
int t(0);cin>>t;
while(t--) solve();
}Bu kodu üstün körü inceleyelim. Gözümüze ilk çarpan şey double looplar olacaktır, bunlardan daha karmaşık bir şey göremiyoruz. Ancak belki looplar bellir bir durumda "İkiye bölerek" işlem yapıyordur. Bakıyoruz öyle bir durumda söz konusu değil, o halde bu algoritma öbeğinin karmaşıklığı O(n^2) diyebiliriz.
Big-O notasyonu bu kadardı, bir sürü atladığım alt başlıklar oldu acemiliğime vermenizi temmeni ediyor buraya kadar okuduğunuz için teşekkür ediyorum.
Kaynakça: https://tr.wikipedia.org/wiki/Büyük_O_gösterimi https://medium.com/kodcular/nedir-bu-big-o-notation-b8b9f1416d30 https://developerinsider.co/big-o-notation-explained-with-examples/
Son düzenleme:
