Algorithms

last edited Sat, 04 Jan 2025 08:22:23 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 operations 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

There is no way to complete the algorithm without visiting each city/node at least once, leading to worst-case runtime O(n!).

Sorting direct link to this section

Quicksort

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
• Divide and Conquer 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 runtime
• Divide and Conquer worst case: O(nlogn)

Selection Sort

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

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

Worst Case: O(n^2)

Bubble Sort

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

Searching direct link to this section

Binary Search

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

Breadth First Search

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

a binary search is superior