Büyük-O Notasyonu

Büyük O gösterimi veya notasyonu, algoritmaların verimliliğinin ifade edilmesinde kullanılır. Bu notasyon, bir algoritmanın zaman veya bellek gereksinimlerinin, işlenecek veri kümesinin eleman sayısı (n) arttıkça nasıl arttığını açıklayan matematiksel bir gösterimdir. Başka bir deyişle veri kümesinin büyüklüğünün algoritmanın performansına olan etkisi ifade edilmeye çalışılır. Bu doğrultuda kullanılan algoritma açısından, hem zaman hem de alan maliyetleri incelenir.

Veri kümesi büyüklüğündeki artışın, bellek kullanımına dair gereksinim artışını gösteren kavrama alan karmaşıklığı (space comlexity) adı verilir. Zaman karmaşıklığı (time complexity) ise bir algoritmanın n sayısı büyüdükçe tamamlaması gereken maksimum adım sayısını ifade eder. Bu bağlamda veri kümesindeki eleman sayısı artışının, algoritmanın zaman maliyetine olan etkisinin nasıl değişeceğidir.

Büyük O notasyonu ile her iki kavramın da ifade edilmesi ve algoritmanın, veri boyutları büyüdükçe performansının ne kadar karmaşıklaştığının ortaya konması mümkün olur.

Örnek vermek gerekirse, bir sınıftaki öğrenciler bir veri kümesi ve öğrenci sayısı da eleman sayısı olabilir. Buna göre öğrencilerin ortalamasının hesaplanması öğrenci sayısına bağlıdır. Buradaki zaman karmaşıklığı O(n) olacaktır. Öğrenciler arasından belli biri aranıyorsa bu durumda tüm sınıftaki kişilerin gözden geçirilmesi gerekecektir. Yine zaman karmaşıklığı aynı değerde olur. Okuldaki öğrencilerin isminin tek tek yazdırılması ve ortalamalarının hesaplanması gerekiyorsa, bu durumda öğrenci sayısının iki katı kadar işlemler tekrarlanacak olmasına rağmen 2n ile n arasında çok büyük fark olmadığından zaman karmaşılığı yine O(n) olarak gösterilecektir. Diğer yandan iki döngünün iç içe girdiği ve eleman sayısının karesi kadar işlem yapıldığı durumlarda zaman karmaşıklığı O(n^2) olacaktır. Diğer durumların aksine, eleman sayısı kaç olursa olsun tek işlem yapılıyorsa, bu durumda zaman karmaşıklığı O(1) olacaktır.

Algoritmanın çalışma performansı büyük O notasyonunun büyüklüğüne göre değerlendirilebilir. Girdi sayısı arttıkça, başka bir deyişle veri setinin boyutu artttıkça, algoritmaların performansları etkilenebilmektedir. Bu kapsamda en iyi zaman karmaşıklığı sabit zamanda çalışan algoritmalara aittir. Yani veri boyutuna göre çalışma performansı değişiklik göstermemektedir. Karmaşıklığın fazla büyüdüğü bir durum ideal bir durum değildir, veri boyutu arttıkça karmaşıklık örneğin üssel bir şekilde artıyorsa algoritmanın performansının kötüleştiği yani verimsizleştiği anlamına gelir.

Kaynakça:

Althoff, C. (2022). The self-taught computer scientist : the beginner’s guide to data structures & algorithms

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms

Mailund, T. (2021). Introduction to Computational Thinking: Problem Solving, Algorithms, Data Structures, and More

Çölkesen, R. (2017). Algoritmalar. In T. R. Çölkesen & O. Aliefendioğlu (Eds.), Bilgisayar Bilimine Giriş (pp. 201–247).