Veri yapısında büyük o gösterimi: Bilinmesi gereken her şey

Bir veri yapısındaki Big O Notasyonu, bir algoritmanın verimliliğini, girdinin büyümesiyle işlevi çalıştırmak için gereken süreyi ve işlevin ne kadar iyi ölçeklendiğini belirlemek için kullanılır. Bu verimliliği ölçmek, uzay karmaşıklığı ve zaman karmaşıklığı olmak üzere iki kısma ayrılabilir.

Büyük O notasyonu, bir argüman belirli bir değere veya sonsuzluğa yönelmeye daha yatkın olduğunda, herhangi bir fonksiyonun sınırlayıcı bir faktörü olarak hareket eden matematiksel gösterimi ifade eder. Edmund Landau, Paul Bachmann ve diğerleri tarafından icat edilen matematiksel gösterimler kategorisine aittir. Bu nedenle, topluca Bachmann-Landau notasyonu veya asimptotik notasyon olarak adlandırılır.

Matematiksel kesintiye göre, iki fonksiyon, f(n) ve g(n) , bağlı olmayan bir pozitif veya gerçek sayılar kümesinde tanımlanır. Burada g(n) , n'nin her büyük değeri için kesinlikle pozitiftir. Aşağıdaki şekilde yazılabilir:

f(n) = O(g(n)) burada n sonsuzluğa eğilimlidir (n → ∞)

Bununla birlikte, burada n'nin sonsuza kadar olduğu varsayımı özel olarak tanımlanmamıştır ve bu nedenle yukarıdaki ifade şu şekilde yazılabilir:

f(n) = O(g(n))

Burada f ve g, pozitif tam sayılardan negatif olmayan gerçek sayılara doğru başlayan gerekli fonksiyonlardır.

Bu nedenle, büyük n değerleri Big O asimptotik ile gösterilir.

Veri Yapısında Big O Notasyonunun Özellikleri

Veri yapısındaki Big O algoritması, zorunlu olarak gerekli birkaç özelliğe sahiptir. Big O Notasyonunun söz konusu temel özellikleri aşağıdaki gibidir:

• Toplama Fonksiyonu:
  f(n) = f 1 (n) + f 2 (n) + — + f m (n) ve f ben (n)≤ f ben +1(n) ∀ i=1, 2,–, m,
  sonra O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Logaritmik İşlev:
  f(n) = logan ve g(n)=logbn ise,
  sonra O(f(n))=O(g(n))
• Sabit Çarpma:
  Eğer f(n) = cg(n), o zaman O(f(n)) = O(g(n)) ki burada c sıfırdan farklı bir sabittir.
• Polinom fonksiyonu:
  f(n) = a0 + a1.n + a2.n2 + — + am.nm ise,
  sonra O(f(n)) = O(nm).

Dünyanın En İyi Üniversitelerinden Online Yazılım Geliştirme Kursları öğrenin . Kariyerinizi hızlandırmak için Yönetici PG Programları, Gelişmiş Sertifika Programları veya Yüksek Lisans Programları kazanın.

Popüler Yazılım Mühendisliği Kurslarımızı keşfedin

Burada Big O adreslenirken, her bir log fonksiyonu benzer şekilde artar.

Algoritmaların Çalışma Zamanı Analizinde Big O Notasyonunun Önemi

Algoritmanın en kötü durum çalışma süresinin karmaşıklığı, özellikle bir algoritmanın performansının analiz edilmesi durumunda, karşılaştırmalar yapmak ve hesaplamak için kullanılır. Sabit Çalışma Süresi olarak gösterilen O(1) sırası, algoritmanın en hızlı çalışma süresidir - algoritmanın aldığı süre, çeşitli giriş boyutları için aynıdır. Bir algoritmanın ideal çalışma zamanının, algoritmanın çalışma zamanı n'nin giriş boyutuna bağlı olduğundan çok nadiren elde edilen sabit çalışma zamanı olduğuna dikkat etmek önemlidir.

Örneğin:

Yukarıda bahsedildiği gibi, bir algoritmanın çalışma zamanı performansı büyük ölçüde n'nin girdi boyutuna bağlıdır. Çeşitli n boyutları için bir algoritmanın çalışma zamanı analizini yapmak için bu gerçeği birkaç matematiksel örnekle açıklayalım:

• sayı = 20
  günlük (20) = 2.996;
  20 = 20;
  20 günlük (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2.432902 + 18 18 ;
• sayı = 10
  günlük (10) = 1;
  10 = 10;
  10 günlük (10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

Bir algoritmanın çalışma zamanı performansı benzer şekilde hesaplanır.

İşte çalışma zamanı analizinin birkaç algoritmik örneği –

• Doğrusal Arama söz konusu olduğunda, çalışma zamanı karmaşıklığı O(n)'dir.
• İkili arama için çalışma zamanı karmaşıklığı O(log n)'dir.
• Seçim Sıralaması, Kabarcık Sıralaması, Kova Sıralaması, Ekleme Sıralaması için çalışma zamanı karmaşıklığı O(n^c)'dir.
• Tower of Hanoi gibi Üstel algoritmalar söz konusu olduğunda, çalışma zamanı karmaşıklığı O(c^n)'dir.
• Merge SortSort ve Heap Sort için çalışma zamanı karmaşıklığı O(n log n)'dir.

Big O, uzay karmaşıklığını nasıl analiz eder?

Bir algoritma için hem alan hem de çalışma zamanı karmaşıklığını belirlemek önemli bir adımdır. Bunun nedeni, algoritmanın çalışma zamanı performansını ve algoritmanın aldığı bellek alanını analiz ederek bir algoritmanın aldığı yürütme süresini, algoritmanın alan karmaşıklığının analizi yoluyla belirleyebilmemizdir. Bu nedenle, bir algoritmanın uzay karmaşıklığını ölçmek için algoritmanın en kötü durum uzay karmaşıklığı performansını karşılaştırmamız gerekir.

Bir algoritmanın uzay karmaşıklığını belirlemek için şu iki görevi izlemeliyiz –

Görev 1: Programı belirli bir algoritma için uygulamak çok önemlidir.

Görev 2: Her bir öğenin tutacağı belleği belirlemek için n girişinin boyutunu bilmek önemlidir.

Bu iki temel görev, bir algoritma için uzay karmaşıklığını hesaplamadan önce gerçekleştirilmelidir.

Uzay Karmaşıklık Algoritmaları Örnekleri

Bu tür bir algoritmanın daha iyi anlaşılması için bazıları aşağıda belirtilen uzay karmaşıklığına sahip birçok algoritma örneği vardır:

• Kabarcık sıralama, Doğrusal Arama, Seçim sıralama, Ekleme sıralama, Yığın sıralama ve İkili Arama için alan karmaşıklığı O(1)' dir .
• Radix sort söz konusu olduğunda , uzay karmaşıklığı O(n+k) şeklindedir .
• Hızlı Sıralama için alan karmaşıklığı O(n) 'dir.
• Alan karmaşıklığı, birleştirme sıralaması için O(log n) 'dir.

C Büyük O Notasyonu Örneği

Big O notasyonunun öncelikle Bilgisayar Bilimlerinde bir algoritmanın karmaşıklığını veya performansını belirlemek için kullanıldığı bir gerçektir. Bu gösterim, girdi verilerinin kapsamı genişlediğinde, bellek alanının büyümesine veya yürütme süresi gereksinimlerine dayalı olarak algoritmaların davranışını sınıflandırma yeteneği sağlar. Gerçek bellek kullanımını veya yürütme süresini tahmin etmek için değil, algoritmaları karşılaştırmak ve ardından iş için aralarından en iyisini seçmek için tasarlanmıştır. Dile özgü değildir, ancak C'de de uygulanır.

Aşağıda, algoritmanın en kötü durum karmaşıklığının (Büyük O notasyonu) hesaplandığı C'deki seçim sıralama algoritmasını bulacaksınız: -

for(int i=0; i<n; i++)

{

int min = ben;

for(int j=i; j<n; j++)

{

if(dizi[j]<dizi[dk])

min=j;

}

int temp = dizi[i];

dizi[i] = dizi[dk];

dizi[dk] = sıcaklık;

}

Algoritmayı analiz etmek için:

• Dış döngü aralığının, döngü sırasının O(n) olduğunu belirten i < n olduğu zaten belirtilebilir.
• Daha sonra, iç for döngüsü için j < n olarak O(n) olduğunu da belirleyebiliriz.
• Bir c sabiti için ortalama verim n/2 bulunsa bile, sabit yok sayılır. Yani sıra O(n)'dir.
• İç döngü ve dış döngünün sırasını çarptıktan sonra, elde edilen çalışma zamanı karmaşıklığı O(n^2) olur.

C'deki diğer algoritmalar kolayca uygulanabilir, burada karmaşıklıklar kolayca analiz edilebilir ve benzer şekilde belirlenebilir.

Big O Notasyonu Kullanımı

Big O Notation'ın uygulandığı iki ana alan vardır: -

• Matematik : Büyük O Notasyonu, özellikle asimptotik açılım veya kesik Taylor serileri söz konusu olduğunda, sonlu bir serinin bir fonksiyona nasıl yakın olduğunu açıklamak için matematik alanında oldukça yaygın olarak kullanılır.
• Bilgisayar bilimi: Big O notasyonunun, algoritmaların analizindeki kullanışlılığı nedeniyle çoğunlukla bilgisayar bilimi alanında kullanıldığı iyi bilinen bir gerçektir.

Bununla birlikte, her iki uygulamada da, O (·) içinde görünen g ( x ) fonksiyonu , alt mertebeden terimler ve sabit faktörler atlanırsa, muhtemelen en basit olarak seçilir.

Bu gösterimin resmi olarak birbirine yakın fakat nispeten farklı iki kullanımı daha vardır. Bunlar:-

• sonsuz asimptotik
• Sonsuz küçük asimptotikler.

Bununla birlikte, bu ayrım prensipte değildir, uygulamada sadece “Büyük O”nun biçimsel tanımı her iki durum için de tamamen aynıdır. Tek fark, işlevin argümanının sınırlarıdır.

Yazılım Geliştirme ile ilgili Popüler Makalelerimizi okuyun

Çözüm

Sonuç olarak, Big Data'nın veri yapılarında ayrılmaz bir rol oynadığını ve Big O notasyonu hakkında derinlemesine, kapsamlı bilgiye sahip olmanın mükemmel bir beceri seti olduğunu söyleyebiliriz. İş sektöründe yüksek talep görmektedir ve potansiyel olarak bir kariyer yolu için mükemmel bir seçim olabilir. upGrad'ın Büyük Verideki Gelişmiş Sertifika Programı , kariyerinizi ilerletmek için ihtiyacınız olan kaldıracı size sağlayacaktır. PySpark ile Veri İşleme, Veri Ambarı, MapReduce, AWS Bulutta Büyük Veri İşleme, Gerçek Zamanlı İşleme vb. gibi en iyi profesyonel becerileri size tanıtacaktır.