algorithms

last edited Wed, 24 Jul 2024 05:21:40 GMT
backlinks: null

Analysis direct link to this section

An algorithm's efficiency is measured in two ways.

Time Complexity direct link to this section

The amount of time it takes for each statment in an algorithm to complete. Speed does not refer to time but the number of increasing operations, run-time against the size of input is analyzed with the worst case scenario in mind.

input size refers to the number of items in the input
running time the number of primitive operaations executed

void fun(int n){
    int i, j,  k, count =  0;
    for(i = n/2; i <= n; i++)
        for(j = 1; j+n/2 <= n; j++)
            for(k = 1;  k <= n; k = k*2)
                count++;
}

• integer declarations are constant O(1)
• loop one O(n)

Space Complexity direct link to this section

The amount of memory used by a program to execute it is represented by its space complexity. Mainly dependent on hardware.

Space Complexity = Auxillary Space + space used by input

Recursion direct link to this section

Technique used in various algorithms. Problems solved with while loops can often be solved uusing recursion but there doesn't seem to be any significant performance gain.

1. base case
   • when function won't call
2. recursive case
   • function calls itself

def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_key(item)
        elif item.is_a_key():
            print "found the key!"

Types direct link to this section

Gale-Shapely direct link to this section

Traveling Salesman direct link to this section

Worst Case: O(n!)

Binary Search direct link to this section

1. pick middle of the index and test it against the key
2. terminate if the middle index matches the key, otherwise move on to the left or right of the remaining search space and repeat

• If the key is smaller than the middle element, then the left side is used for next search.
• If the key is larger than the middle element, then the right side is used for next search.
• implemented with recursion or iteration
• • can only be performed in contiguous memory, requires items to be sorted for comparison

worst case: O(logn) sublinear

Quicksort direct link to this section

a pivot is chosen and then a partition() occurs recursively on both sides of the pivot

• speed ultimately depends on pivot
• efficient for large datasets
• divide and conquer algorithm
• not stable, two matching data entries with the same key will pose problems

Signs of an ideal pivot:

1. correct position in final sorted array
2. items to the left are smaller
3. items to right are larger

def quicksort(array):
    if len(array)  < 2:
        return array
    else: 
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)
        print quicksort([10, 5, 2, 3])

worst case: O(n^2) if pivot is poorly chosen
best case: O(nlogn)

Mergesort

• an array is divided in half into multiple subarrays
• subarrays are merged and sorted into a new array
• considered superior to Quicksort due to its superior worst case worst case: O(nlogn)

Selection Sort direct link to this section

two nested loops to sort a list

1. traverse through list once and find minimum
2. swap place with min or max of list
3. repeat until end of list

• optimal for small datasets
• slow algorithm worst case: O(n^2)

Insertion Sort direct link to this section

1 for j = 2 to A.length
2   key = A[j]
3   // Insert A[j] into the sorted sequence A[1...j - 1]
4   i = j - 1
5   while i > 0 and A[i] > key
6       A[i + 1] = A[i]
7       i = i - 1
8   A[i + 1] = key

Worst Case: O(n^2)

Bubble Sort direct link to this section

1. traverse from left and compare two adjacent elements
2. bigger element moved to the right
3. continue across entire list

Breadth First Search direct link to this section

A type of graph and search algorithm. Will find the shortest path if one exists. Running time will be O(n + m) where n is the number of vertices and m is the number of edges

• each vertex of the graph is either visted or not visted
• queue is used as data structure for traversal

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print person + " is a mango seller"
             return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

Simple Search direct link to this section

a binary search is superior