Karmaşıklık Sırası, bilgisayar bilimlerinde bir algoritmanın veya programın verimliliğini ölçmek için kullanılan bir terimdir. Bir sorunu çözmek veya bir görevi gerçekleştirmek için gereken zaman ve kaynak miktarını ifade eder. Programlamada Karmaşıklık Sırası genellikle şu şekilde ifade edilir: Büyük O Bir algoritmanın zaman veya alan gereksinimlerine ilişkin bir üst sınır veren gösterim. Bu yazımızda C programlama dilinde Karmaşıklık Sırasını ve önemini tartışacağız.
C Programlama Dilinde Karmaşıklık Sırası:
C programlamada, bir algoritmanın Karmaşıklık Sırası, program tarafından gerçekleştirilen işlem sayısına bağlıdır. Örneğin, n boyutunda bir dizimiz varsa ve dizide belirli bir öğeyi aramak istiyorsak, algoritmanın Karmaşıklık Sırası, dizideki öğelerin sayısına bağlı olacaktır. Eğer bir performans sergilersek Doğrusal Arama dizi aracılığıyla Karmaşıklık Sırası şu şekilde olacaktır: Açık) Bu, öğeyi aramak için gereken sürenin dizinin boyutuyla doğrusal olarak artacağı anlamına gelir. Eğer bir kullanırsak İkili Arama Algoritması bunun yerine Karmaşıklık Sırası şu şekilde olacaktır: O(log n) Bu, öğeyi aramak için geçen sürenin dizinin boyutuyla birlikte logaritmik olarak artacağı anlamına gelir.
Benzer şekilde diğer algoritmaların Karmaşıklık Sırası, örneğin Sıralama Algoritmaları , Grafik Algoritmaları , Ve Dinamik Programlama Algoritmaları ayrıca programın gerçekleştirdiği işlem sayısına da bağlıdır. Bu algoritmaların Karmaşıklık Sırası şu şekilde ifade edilebilir: Büyük O notasyon.
Bazı yaygın karmaşıklık düzeylerine ve bunlara karşılık gelen algoritmalara bir göz atalım:
Bu, algoritmanın girdi boyutundan bağımsız olarak sabit bir süre harcadığı anlamına gelir. Örneğin bir dizideki bir öğeye erişim Ç(1) zaman, çünkü öğeye indeksi kullanılarak doğrudan erişilebilir.
Bu, algoritmanın harcadığı zamanın girdi boyutuyla birlikte logaritmik olarak arttığı anlamına gelir. Bu yaygın olarak görülür Böl ve Fethet Algoritmaları beğenmek Ikili arama , sorunu çözmek için girişi daha küçük parçalara böler.
Bu, algoritmanın harcadığı zamanın girdi boyutuyla doğrusal olarak arttığı anlamına gelir. Bu tür algoritmaların örnekleri şunlardır: Doğrusal Arama Ve Kabarcık Sıralaması .
Bu, algoritmanın harcadığı zamanın n'nin logaritması ile çarpılmasıyla n kadar arttığı anlamına gelir. Bu tür algoritmaların örnekleri şunlardır: Hızlı sıralama Ve Birleştirme sıralaması .
Bu, algoritmanın harcadığı zamanın girdi boyutuyla birlikte karesel olarak arttığı anlamına gelir. Bu tür algoritmaların örnekleri şunlardır: Kabarcık Sıralaması Ve Ekleme Sıralaması .
Bu, girdi boyutundaki her artışla algoritmanın harcadığı zamanın iki katına çıktığı anlamına gelir. Bu yaygın olarak görülür Özyinelemeli Algoritmalar gibi Fibonacci Serisi .
Karmaşıklık Sırasının yalnızca algoritmanın harcadığı süreye ilişkin bir üst sınır sağladığını bilmek önemlidir. Girdi verilerine ve algoritmanın uygulanmasına bağlı olarak, harcanan gerçek süre bu sınırdan çok daha az olabilir.
C programlamada, bir algoritmanın Karmaşıklık Sırası, kodun analiz edilmesi ve gerçekleştirilen işlem sayısının sayılmasıyla belirlenebilir. Örneğin, n boyutunda bir dizi boyunca yinelenen bir döngümüz varsa, döngünün zaman karmaşıklığı şu şekilde olacaktır: Açık) . Benzer şekilde, kendisini k kez çağıran özyinelemeli bir fonksiyonumuz varsa, fonksiyonun zaman karmaşıklığı şu şekilde olacaktır: Ç(2^k) .
Bir programın performansını optimize etmek için, daha düşük Karmaşıklık Sırasına sahip algoritmaların seçilmesi önemlidir. Örneğin, bir diziyi sıralamamız gerekiyorsa, aşağıdaki gibi daha düşük karmaşıklığa sahip bir Sıralama algoritması kullanmalıyız: Hızlı sıralama veya Birleştirme sıralaması , ziyade Kabarcık Sıralaması , daha yüksek düzeyde karmaşıklığa sahiptir.
Karmaşıklık Sırasının Analizi:
Bir algoritmanın Karmaşıklık Sırasını analiz etmek için, girdi boyutu arttıkça çalışma süresinin veya alan kullanımının nasıl büyüdüğünü belirlememiz gerekir. Bunu yapmanın en yaygın yöntemi algoritmanın gerçekleştirdiği temel işlemlerin sayısını saymaktır.
Temel işlem, iki sayı eklemek veya bir dizi öğesine erişmek gibi gerçekleştirilmesi sabit miktarda zaman alan bir işlemdir. Algoritma tarafından gerçekleştirilen temel işlemlerin sayısını girdi boyutunun bir fonksiyonu olarak sayarak Karmaşıklık Sırasını belirleyebiliriz.
Örneğin, ilk n tamsayının toplamını hesaplayan aşağıdaki C fonksiyonunu düşünün:
C Kodu:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>