ข้ามไปยังเนื้อหาหลัก

Analyzing Complexity of Code through Python

Get introduced to Asymptotic Analysis. Learn more about the complexity of the algorithm as well as asymptotic notation, such as Big O, Big θ, and Big Ω notation. Along with the examples of complexity in a different algorithm.
· 11 นาที อ่าน

สำรวจด้วย AI

The complexity of an algorithm is a measure of the amount of time and/or space required by an algorithm for an input of a given size (n). Though the complexity of the algorithm does depends upon the specific factors such as: The architecture of the computer i.e.the hardware platform representation of the Abstract Data Type(ADT) compiler efficiency the complexity of the underlying algorithm size of the input. Though you will see most significant factors are a complexity of underlying algorithm and size of the input.

In DataCamp's blog Python Data Structures Tutorial you can learn about the basic overview of data structure and the implementation of the data structure in Python in that blog. The blog post gives an introduction to the basic data structure of Python. With it, you'll discover Abstract Data Type and Data Structure, Primitive Data Structure and Non-Primitive Data Structure.

Asymptotic Analysis

Asymptotic analysis refers to the computing of the running time of any piece of code or the operation in a mathematical unit of a computation. Its operation is computed in terms of a function like f(n). In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.

The time required by the algorithm falls under the three types: Worst case - Maximum time required by an algorithm and it is mostly used or done while analyzing the algorithm. Best case - Minimum time required for the algorithm or piece of code and it is not normally calculated while analyzing the algorithm. Average case - Average time required for an algorithm or portion of code and it is sometimes done while analyzing the algorithm.

Asymptotic notation

The commonly used notation for calculating the running time complexity of the algorithm is as follows:

  • Big O notation
  • Big θ notation
  • Big Ω notation

Big Oh Notation, Ο

Big O is used to measure the performance or complexity of an algorithm. In more mathematical term, it is the upper bound of the growth rate of a function, or that if a function g(x) grows no faster than a function f(x), then g is said to be a member of O(f).In general, it is used to express the upper bound of an algorithm and which gives the measure for the worst time complexity or the longest time an algorithm possibly take to complete.

Big Omega Notation, Ω

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

Big Theta Notation, θ

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time.

Notation is used to determine the complexity of various algorithm's

Big O notation is mostly used, and it is used mainly all the times to find the upper bound of an algorithm whereas the Big θ notation is sometimes used which is used to detect the average case and the Ω notation is the least used notation among the three.

You will be seeing the examples of the notation used in the algorithm to determine the complexity for that particular algorithm.

For example for a quick sort:

Quick sort is a Divide and Conquer algorithm where it is used for sorting. It serves as a systematic method of placing elements in the order, i.e. For example arranging elements or number in the array in ascending or descending order. This algorithm picks the pivot or the index that is chosen from the given array. Also, the pivot can be selected in the different ways. The example that is implemented below is the pivot element selected with the last element.

The main crux of the Quick sort is the partition. From an array, a partition element is chosen, and then the partition element(i.e.pit for example) is kept in correct position and then the element greater to the partition is kept at the right of the pit, and the smaller element is kept at the left of the pit.

#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"