Complexiteit van code analyseren met Python

De complexiteit van een algoritme is een maat voor de hoeveelheid tijd en/of ruimte die een algoritme nodig heeft voor een invoer van een bepaalde grootte (n). De complexiteit van het algoritme hangt wel af van specifieke factoren, zoals: de architectuur van de computer, d.w.z. het hardwareplatform, de representatie van het Abstract Data Type (ADT), de efficiëntie van de compiler, de complexiteit van het onderliggende algoritme en de grootte van de invoer. Je zult echter zien dat de belangrijkste factoren de complexiteit van het onderliggende algoritme en de grootte van de invoer zijn.

In DataCamp’s blog Python Data Structures Tutorial leer je de basis van datastructuren en hoe je ze in Python implementeert. De blogpost geeft een introductie tot de basisdatastructuren van Python. Je ontdekt er Abstract Data Type en Data Structure, Primaire datastructuren en Niet-primaire datastructuren.

Asymptotische analyse

Asymptotische analyse verwijst naar het berekenen van de looptijd van een stuk code of een bewerking in een wiskundige eenheid van een berekening. De bewerking wordt uitgedrukt in termen van een functie zoals f(n). In de wiskundige analyse is asymptotische analyse, ook wel asymptotiek genoemd, een methode om grensgedrag te beschrijven.

De tijd die een algoritme nodig heeft, valt onder drie typen: Worstcasescenario – Maximale tijd die een algoritme nodig heeft en wordt meestal gebruikt bij het analyseren van het algoritme. Bestcasescenario – Minimale tijd die een algoritme of stuk code nodig heeft en wordt normaal gesproken niet berekend bij het analyseren van het algoritme. Gemiddelde geval – Gemiddelde tijd die een algoritme of stuk code nodig heeft en wordt soms gebruikt bij het analyseren van het algoritme.

Asymptotische notatie

De gangbare notaties voor het berekenen van de tijdscomplexiteit van een algoritme zijn:

• Big O-notatie
• Big θ-notatie
• Big Ω-notatie

Big Oh-notatie, Ο

Big O wordt gebruikt om de prestaties of complexiteit van een algoritme te meten. In meer wiskundige termen is het de bovengrens van de groeisnelheid van een functie, oftewel: als een functie g(x) niet sneller groeit dan een functie f(x), dan is g een element van O(f). In het algemeen gebruik je het om de bovengrens van een algoritme uit te drukken, wat de maat geeft voor de slechtste tijdscomplexiteit of de langst mogelijke tijd die een algoritme nodig kan hebben om te voltooien.

Big Omega-notatie, Ω

De notatie Ω(n) is de formele manier om de ondergrens van de looptijd van een algoritme uit te drukken. Het meet de beste tijdscomplexiteit, oftewel de kortst mogelijke tijd die een algoritme nodig kan hebben om te voltooien.

Big Theta-notatie, θ

De notatie θ(n) is de formele manier om zowel de ondergrens als de bovengrens van de looptijd van een algoritme uit te drukken.

Notatie wordt gebruikt om de complexiteit van verschillende algoritmen te bepalen

Big O-notatie wordt het meest gebruikt en vrijwel altijd ingezet om de bovengrens van een algoritme te vinden, terwijl de Big θ-notatie soms wordt gebruikt om het gemiddelde geval te bepalen en de Ω-notatie het minst gebruikt wordt van de drie.

Je ziet hieronder voorbeelden van notaties die in algoritmen worden gebruikt om de complexiteit van dat specifieke algoritme te bepalen.

Bijvoorbeeld voor quicksort:

Quicksort is een Divide and Conquer-algoritme dat wordt gebruikt voor sorteren. Het biedt een systematische manier om elementen op volgorde te plaatsen, bijvoorbeeld elementen of getallen in een array in oplopende of aflopende volgorde. Dit algoritme kiest een pivot, oftewel een index die wordt gekozen uit de gegeven array. De pivot kan op verschillende manieren worden geselecteerd. In het onderstaande voorbeeld is het pivotelement gekozen als het laatste element.

De kern van quicksort is de partitionering. Uit een array wordt een partitioneringselement gekozen, waarna het partitioneringselement (bijv. pit in dit voorbeeld) op de juiste positie wordt gezet; elementen groter dan de pivot komen rechts van de pivot, en kleinere elementen links.

#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]),

The Sorted array is:
2
4
6
8
10
12
Je krijgt de output:

The Sorted array is: 2 4 6 8 10 12

Nu is het tijd om de tijdscomplexiteit te analyseren. Eerst:

• Het bestcase is: Ω(n log(n))
• Het gemiddelde geval is: Θ(n log(n))
• Het worstcase is: O(n^2)

Laten we nu de bovenstaande code analyseren.

Bestcase: Dit is het geval waarin het partitioneringselement het middelste element als pivot kiest. Omdat het algoritme recursief wordt aangeroepen op de eerste en tweede helft, is het totale aantal benodigde stappen gelijk aan het aantal keren dat je van n naar 1 gaat als je het probleem bij elke stap door 2 deelt. Dus er zijn n/2/2/2/2/..../2=1 *k keer. Let echter op dat de vergelijking eigenlijk is: n / 2^k = 1. Aangezien 2^logn = n, krijgen we k = logn. Dus het aantal stappen (iteraties) dat het algoritme nodig heeft is O(log n), wat het algoritme O(n log n) maakt – omdat elke iteratie O(n) is.

Gemiddeld geval: Voor het gemiddelde geval moeten we alle permutaties van de array beschouwen en de tijd berekenen die elke permutatie kost. Je kunt hierover meer lezen op Merge sort.

Worstcase: In het worstcase, als het eerste element als pivot wordt gekozen, treedt het slechtste geval op wanneer de invoer die gesorteerd moet worden in oplopende of aflopende volgorde staat. De reden voor het worstcase is dat na het partitioneren de ene partitie grootte 1 heeft en de andere n-1. Hier is T(n) de functie: De tijd om ‘n’ elementen te quicksorten T(n) = tijd om ‘n’ elementen te partitioneren O(n) + tijd om ‘n-1’ elementen te quicksorten T(n-1). Dus T(n) = T(n-1) + O(n) => T(n) = O(n^2)

Voorbeelden

De onderstaande code is misschien niet heel spannend en je zou het geen algoritme noemen, maar je kunt het wel als algoritme beschouwen, omdat elke code die iets doet technisch gezien een algoritme is en een manier om een bepaald probleem op te lossen. Het algoritme dat je hieronder ziet is het gebruik van een for-loop met één print-statement.

print('I love Python');

Hello world!
De tijdscomplexiteit van het bovenstaande algoritme is O(1) omdat het altijd één stap kost. Het is constante tijd.

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 Hoe zou je de efficiëntie van het bovenstaande algoritme beschrijven in Big O-notatie?

Om het bovenstaande algoritme te analyseren, moet je nagaan hoeveel stappen dit algoritme neemt. In het bovenstaande geval staan er vier items in een lijst en moet je elk item één keer afdrukken. Maar wat als er meer dan 4 items in de lijst staan, bijvoorbeeld 15? Zou de for-loop dan hetzelfde aantal stappen nemen voor 15 items in een lijst? Omdat deze for-loop evenveel stappen neemt als er elementen zijn, zeg je dat het algoritme een efficiëntie van O(N) heeft in plaats van O(1).

Het volgende voorbeeld is een eenvoudig Python-algoritme om te bepalen of een getal priem is:

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

De bovenstaande code accepteert een getal als argument en start een for-loop waarin je elk getal van 2 tot en met dat getal deelt en kijkt of er een rest is. Als er geen rest is, weet je dat het getal niet priem is en geef je meteen False terug. Als je helemaal tot aan het getal komt en steeds een rest vindt, weet je dat het getal priem is en geef je True terug.

Je kunt de efficiëntie van het bovenstaande algoritme bepalen als O(N). Het bovenstaande voorbeeld neemt geen gegevens in de vorm van een array of lijst, maar het getal wordt als argument doorgegeven. Als je een willekeurig getal zoals 11 doorgeeft, loopt de for-loop ongeveer elf stappen. (In feite negen stappen, omdat hij bij twee begint en vlak voor het daadwerkelijke getal eindigt.) Voor het getal 101 loopt de loop ongeveer 101 stappen. Omdat het aantal stappen in de pas toeneemt met het getal dat in de functie wordt doorgegeven, is dit een klassiek voorbeeld van O(N).

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

In de bovenstaande code is de complexiteit van het algoritme O(N). Omdat de tweede loop 100 als argument heeft, kan die worden genegeerd, omdat je de complexiteit uitdrukt onder de aanname dat N zeer groot is.

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

Er zijn twee loops waarbij de lengte van de ene loop m is en de lengte van de andere n. Ook moet je aannemen dat m en n groot zijn; dan is de complexiteit van de bewerking O(n+m). Omdat de loops verschillend zijn en verschillende input aannemen, is de complexiteit additief van aard.

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

Er is een geneste for-loop, en opnieuw neem je aan dat n en m groot zijn; dan is de complexiteit van de bewerking O(n*m). Omdat de loops hetzelfde zijn en genest, is de complexiteit multiplicatief van aard.

Gefeliciteerd!

Je bent aan het einde van deze tutorial gekomen! Onderweg heb je asymptotische notatie geleerd, een basisinstrument dat door programmeurs en data scientists wordt gebruikt. Je hebt zojuist een eenvoudige manier geleerd om complexiteit te analyseren, gewoon in begrijpelijk Engels, zonder technische termen en strikte wiskunde. Hoewel onderwerpen over datastructuren en algoritmen vaak vooral aan bod komen als je een bachelor informatica of een verwant vakgebied doet, is het voor iedereen belangrijk om hier kennis van te hebben, ook als je geen expert bent. Wil je dieper duiken, kijk dan op deze link: MIT opencourseware Algorithm course

Wil je meer leren over Python? Bekijk dan deze DataCamp-cursussen: