Python ile Kod Karmaşıklığını Analiz Etme

Bir algoritmanın karmaşıklığı, verilen bir boyuttaki (n) girdi için gereken zaman ve/veya bellek miktarının bir ölçüsüdür. Algoritmanın karmaşıklığı, şu gibi belirli etkenlere bağlıdır: Bilgisayarın mimarisi, yani donanım platformu, Soyut Veri Tipinin (ADT) gösterimi, derleyicinin verimliliği, altta yatan algoritmanın karmaşıklığı, girdinin boyutu. Ancak en belirleyici etkenler genellikle altta yatan algoritmanın karmaşıklığı ve girdinin boyutudur.

DataCamp'in Python Veri Yapıları Eğitimi adlı blog yazısında, veri yapılarına genel bir bakış ve Python'da veri yapılarını nasıl uygulayacağınızı öğrenebilirsiniz. Bu yazı, Python'un temel veri yapılarına giriş sağlar. Bununla Soyut Veri Tipi ve Veri Yapısını, İlkel ve İlkel Olmayan Veri Yapılarını keşfedeceksiniz.

Asimptotik Analiz

Asimptotik analiz, herhangi bir kod parçasının veya işlemin çalışma süresini, bir hesaplamanın matematiksel birimi cinsinden hesaplamayı ifade eder. İşlemler, f(n) gibi bir fonksiyonla ifade edilir. Matematiksel analizde asimptotik analiz (asimptotikler olarak da bilinir), sınırlayıcı davranışı tanımlama yöntemidir.

Algoritmanın gerektirdiği süre üç türe ayrılır: En kötü durum - Bir algoritmanın gerektirdiği en fazla süre; algoritma analizinde en çok kullanılan durumdur. En iyi durum - Algoritmanın veya kod parçasının gerektirdiği en az süre; genellikle analizde hesaplanmaz. Ortalama durum - Bir algoritmanın veya kod parçasının gerektirdiği ortalama süre; bazen analiz sırasında değerlendirilir.

Asimptotik gösterim

Algoritmanın çalışma zamanı karmaşıklığını hesaplamak için yaygın olarak kullanılan gösterimler şunlardır:

• Big O gösterimi
• Big θ gösterimi
• Big Ω gösterimi

Big Oh Gösterimi, Ο

Big O, bir algoritmanın performansını veya karmaşıklığını ölçmek için kullanılır. Daha matematiksel bir ifadeyle, bir fonksiyonun büyüme hızının üst sınırıdır; eğer g(x) fonksiyonu f(x) fonksiyonundan daha hızlı büyümezse, g O(f)'nin bir üyesidir. Genel olarak bir algoritmanın üst sınırını ifade etmek için kullanılır ve en kötü zaman karmaşıklığının, yani bir algoritmanın tamamlanmak için alabileceği en uzun sürenin ölçüsünü verir.

Big Omega Gösterimi, Ω

Ω(n) gösterimi, bir algoritmanın çalışma süresinin alt sınırını ifade etmenin resmi yoludur. En iyi durum zaman karmaşıklığını, yani bir algoritmanın tamamlanmak için alabileceği en az süreyi ölçer.

Big Theta Gösterimi, θ

θ(n) gösterimi, bir algoritmanın çalışma süresinin hem alt hem de üst sınırını ifade etmenin resmi yoludur.

Gösterim, çeşitli algoritmaların karmaşıklığını belirlemek için kullanılır

Big O gösterimi çoğunlukla ve genellikle üst sınırı bulmak için kullanılırken, Big θ gösterimi bazen ortalama durumu tespit etmek için kullanılır ve Ω gösterimi bu üçü içinde en az kullanılanıdır.

Belirli bir algoritmanın karmaşıklığını belirlemek için gösterimlerin nasıl kullanıldığına dair örnekleri göreceksiniz.

Örneğin hızlı sıralama (quick sort) için:

Quick sort, sıralama için kullanılan bir Böl ve Fethet algoritmasıdır. Öğeleri belirli bir düzene yerleştirmenin sistematik bir yolunu sunar; örneğin bir dizideki öğeleri artan ya da azalan düzende sıralamak. Bu algoritma, verilen diziden bir pivot veya indeks seçer. Pivot farklı şekillerde seçilebilir. Aşağıda uygulanan örnekte pivot öğesi son öğe olarak seçilmiştir.

Quick sort'un özündeki işlem bölümlendirmedir (partition). Bir diziden bir bölümleme öğesi seçilir, ardından bu öğe doğru konumuna yerleştirilir; bölümlemeden büyük olanlar sağa, küçük olanlar ise sola konur.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

Sıralanmış dizi:
2
4
6
8
10
12
Şu çıktıyı alırsınız:

Sıralanmış dizi: 2 4 6 8 10 12

Şimdi zaman karmaşıklığını analiz etme zamanı. Öncelikle,

• En iyi durum: Ω(n log(n))
• Ortalama durum: Θ(n log(n))
• En kötü durum: O(n^2)

Şimdi yukarıdaki kodu analiz edelim.

En iyi durum: Bölümleme öğesinin orta değeri pivot olarak seçildiği durumdur. Algoritma ilk ve ikinci yarıda özyinelemeli olarak çalıştırılacağından, gerekli toplam adım sayısı, problemi her adımda ikiye böldüğünüzde n'den 1'e ulaşmak için gereken adım sayısıdır. Yani n/2/2/2/2/..../2=1, k kez. Ancak denklem aslında şöyledir: n / 2^k = 1. 2^logn = n olduğundan k = logn elde ederiz. Dolayısıyla algoritmanın gerektirdiği adım (yineleme) sayısı O(log n)'dir; her yineleme O(n) olduğundan algoritma O(n log n) olur.

Ortalama durum: Ortalama durumu yapmak için dizinin tüm permütasyonlarını ele almak ve her permütasyonun aldığı süreyi hesaplamak gerekir. Daha fazlası için Merge sort'a bakabilirsiniz.

En kötü durum: En kötü durumda, ilk öğe pivot olarak seçilirse ve sıralanacak girdi artan veya azalan düzende ise ortaya çıkar. En kötü durumun nedeni, bölümlemeden sonra bir bölümün boyutunun 1, diğerinin ise n-1 olmasıdır. Burada T(n) fonksiyondur: n öğeyi hızlı sıralamak için geçen süre T(n) = n öğeyi bölümlemek için geçen süre O(n) + n-1 öğeyi hızlı sıralamak için geçen süre T(n-1). Yani T(n) = T(n-1) + O(n) => T(n) = O(n^2)

Örnekler

Aşağıdaki kod pek havalı görünmeyebilir ve bir algoritma olarak adlandırılmayabilir; ancak teknik olarak herhangi bir şey yapan her kod bir algoritmadır ve belirli bir problemi çözmenin bir yoludur. Yukarıda gördüğünüz algoritma, tek bir print ifadesi içeren bir for döngüsünün kullanımına bir örnektir.

print('I love Python');

Merhaba dünya!
Yukarıdaki algoritmanın zaman karmaşıklığı O(1)'dir çünkü her zaman tek bir adım alır. Bu, sabit zamandır.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs Yukarıdaki algoritmanın verimliliğini Big O Gösterimi ile nasıl tanımlarsınız?

Yukarıdaki algoritmayı analiz etmek için, bu algoritmanın kaç adım attığını düşünmelisiniz. Bu durumda listede dört öğe var ve her birini bir kez yazdırmanız gerekiyor. Peki listede 4'ten fazla, örneğin 15 öğe olsaydı, for döngüsü 15 öğe için de aynı sayıda adımı mı atardı? Bu for döngüsü, listede kaç öğe varsa o kadar adım attığı için bu algoritmanın verimliliğinin O(1) değil O(N) olduğunu söylemelisiniz.

Bir sonraki örnek, bir sayının asal olup olmadığını belirlemek için basit bir Python tabanlı algoritmadır:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

Yukarıdaki kod, bir sayıyı argüman olarak alır ve 2'den o sayıya kadar her sayıya bölüp kalan olup olmadığını kontrol ettiğiniz bir for döngüsü başlatır. Kalan yoksa, sayının asal olmadığını bilirsiniz ve hemen False döndürürsünüz. Sayıya kadar gelip her seferinde kalan bulursanız, sayının asal olduğunu bilirsiniz ve True döndürürsünüz.

Yukarıdaki algoritmanın verimliliğini O(N) olarak belirleyebilirsiniz. Bu örnek, veriyi bir dizi veya liste şeklinde almaz; fonksiyona geçirilen sayı bir argümandır. Örneğin 11 gibi bir sayı geçirirseniz, for döngüsü yaklaşık on bir adım çalışır. (Aslında iki ile başlayıp sayının hemen öncesinde bittiği için dokuz adım çalışır.) 101 sayısı için döngü yaklaşık 101 adım çalışır. Adım sayısı fonksiyona geçirilen sayıyla aynı oranda arttığından bu, klasik bir O(N) örneğidir.

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

Yukarıdaki kodda algoritmanın karmaşıklığı O(N)'dir. İkinci döngüde argüman olarak 100 bulunsa da, karmaşıklığı N'in çok büyük olduğu varsayımıyla ifade etmeniz gerektiğinden bu göz ardı edilebilir.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

İki döngü vardır; birinin uzunluğu m, diğerinin uzunluğu n'dir. m ve n'in büyük olduğunu varsayarsanız, işlemin karmaşıklığı O(n+m) olur. Döngüler farklı ve girdileri farklı olduğundan karmaşıklık toplayıcı niteliktedir.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

İç içe bir for döngüsü vardır; n ve m'in büyük olduğunu varsayarsanız işlemin karmaşıklığı O(n*m) olur. Döngüler aynı ve iç içe olduğundan karmaşıklık çarpıcı niteliktedir.

Tebrikler!

Bu eğitimin sonuna geldiniz! Bu süreçte, programcılar ve veri bilimciler tarafından kullanılan temel bir araç olan asimptotik gösterimi öğrendiniz. Teknik terimler ve matematiksel sıkılık verilmeden, sade bir dille yazılmış temel ve anlaşılır bir karmaşıklık analiz yöntemini öğrendiniz. Veri yapıları ve algoritmalar genellikle yalnızca bilgisayar bilimi lisans öğrencileri veya ilgili alanlarda okutulsa da, bu konularda uzman olmasanız bile bilgi sahibi olmak eşit derecede önemlidir. Öğrenim yolculuğunuza derinlemesine dalmak için şu bağlantıya bakabilirsiniz: MIT opencourseware Algoritmalar dersi

Python hakkında daha fazla bilgi edinmek isterseniz şu DataCamp kurslarına göz atın: