2022-03-06

The main indicator to evaluate algorithms is the **speed** to process data. The major way to evaluate the speed of the algorithm is** Big O notation**.

Big O notationis a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.(wikipedia: Big O notation)

In other word, Big O(Order) notation is the calculation ability of the functions according to how these run **time** or **space** requirements grow as the **input size grows**. The letter O is used because the growth rate of a function is also referred to as the order of the function.

There are the two key words to understand Big O notation like the below:**Time complexity**: time to finish the function execution**Space complexity**: memory to use for the function execution

**Time complexity is the same as space complexity but the usage is different.**

Representations of Big O notation:O(1) > O(log n) > O(n) >O(n log n)> O(n2) > O(n3) > O(nn)

Coding example

```
# O(1)
def func1(nums):
return nums[0]
# O(log(n))
def func2(nums):
for num in nums:
if num < 1:
return num
else:
print(num)
# O(n)
def func3(nums):
for num in nums:
print(num)
# O(n*log(n))
def func4(nums):
for i in nums:
for j in i:
if j > 15:
print(j)
# O(n**2)
def func5(nums):
for i in nums:
for j in i:
print(j)
```

References of time complexity:

- Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)
- The Ultimate Big O Notation Tutorial (Time & Space Complexity For Algorithms)

There are **two kinds of approaches **and **three algorithms **to process data.

small number -> big number

```
for i in range(5):
print(i)
-> 0,1,2,3,4
```

big number -> small number

```
def recursion(N):
if N < 2:
return N
print(N)
return recursion(N-1)
recursion(5)
-> 5, 4, 3, 2, 1
```

**Brute force**

= for loop

**Divide and Conquer**

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

In short word, divide a problem into a few subproblems or more.=recursion

**Dynamic algorithm**

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. On the top of that, store the result and re-use it.

In short word, divide a problem into a few subproblems or more and re-use the results of them.- recursion or for loop- memoization

**CASE STUDY with Fibonacci Sequence:**

```
# brute force with in-place
def fib(N: int) -> int:
if N < 2:
return N
first, second = 0,1
for i in range(2, N+1):
first, second = second, first + second
return second
# brute force with list
def fib(N: int) -> int:
if N < 2:
return N
fib_seq = [0,1]
for i in range(2, N):
fib_seq.append(fib_seq[i -1] + fib_seq[i -2])
return fib_seq[-1] + fib_seq[-2]
# brute force with memoization and dict
def fib_memoize(N: int) -> int:
if N < 2:
return N
cache = {0:0, 1:1}
for i in range(2, N+1):
cache[i] = cache[i-1] + cache[i-2]
print(cache)
return cache[N]
# brute force with memoization and list
def fib(n):
A = [None] * (n+1)
A[0] = 0
A[1] = 1
for i in range(2, n+1):
print(A)
A[i] = A[i-1] + A[i-2]
return A[n]
# divide and conquer with recursion
def fib(N:int) -> int:
if N < 2:
return N
# divide a problem into subproblem a
a = fib(N-1)
# divide a problem into subproblem b
b = fib(N-2)
# conquer
c = a+b
print(f"a: {a}, b:{b}, c:{c}, n:{n}")
return c
# ===print output of divide and conquer with recursion
# $ python fib.py
# a: 1, b:0, c:1, n:2
# a: 1, b:1, c:2, n:3
# a: 1, b:0, c:1, n:2
# a: 2, b:1, c:3, n:4
# a: 1, b:0, c:1, n:2
# a: 1, b:1, c:2, n:3
# a: 3, b:2, c:5, n:5
# 5
# ===
# recursion with memoization to store the overlapped sub-problems
def fib_memo(n):
# initialize memo
memo = {}
def fib_m(n, memo):
if n == 0 or n == 1:
return n
if n not in memo:
res = fib_m(n-1, memo) + fib_m(n-2, memo) # 1, 0 -> {2: 1}...
memo[n] = res
return res
print(memo)
return memo[n]
return fib_m(n, memo)
# ===print output of recursion with memoization
# {2: 1, 3: 2}
# {2: 1, 3: 2, 4: 3}
# 5
# ===
# dynamic algorithm with memoization
def fib_dynamic(n):
fib = {}
for k in range(1, n+1):
if k <= 2:
f = 1
else:
# re-use
f = fib[k-1] + fib[k-2]
# memoize
fib[k] = f
return fib[n]
```

References of Algorithm:

- Base case — Think of the simplest possible input for this function
- Find the relation — Think how the larger problem can be solved with the help of the solution of the smaller problem
- Generalize —Make a generalized function that solves the problem. Put this all together into a Mathematical function or a Tree.

- Iteration — ex) Linked List in reverse order, Factorial, For loop
- Breaking Into Subproblems — ex) Towers of Hanoi, Fibonacci
- Selection — ex) Knapsack, Word break…etc.
- Ording — ex) Permutationse…etc.
- Divide and Conquer — ex) Mergesort, Generate all BSTs for a set of items
- Depth First Search — ex) Search in a tree…etc.

You should understand the below picture following the code of divide and conquer approach by recursion and the code of recursion with memoization.

Learning sort algorithms can be a good stepping stone to learn the core principle of the algorithms.

This is the basic sort algorithms and the speed ability of each here.

This image is created by Jesse Tetsuya.

**Bubble sort**: a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

```
import random
nums = [random.randint(0,1000) for _ in range(10)]
len_nums = len(nums)
for i in range(1, len_nums):
for j in range(len_nums):
if nums[j] > nums[i]:
nums[j], nums[i] = nums[i], nums[j]
```

**Selection sort**: the selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

```
import random
nums = [random.randint(0,1000) for _ in range(10)]
len_nums = len(nums)
for i in range(len_nums):
min_index = i
for j in range(len_nums):
if nums[j] > nums[min_index]:
nums[j], nums[min_index] = nums[min_index], nums[j]
```

**Insertion sort**: the array elements are compared with each other sequentially and then arranged simultaneously in some particular order.

```
import random
nums = [random.randint(0,1000) for _ in range(10)]
len_nums = len(nums)
for i in range(1, len_nums):
for j in range(i):
if nums[j] > nums[i]:
nums[j], nums[i] = nums[i], nums[j]
```

**Quick sort**: a type of Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot

```
nums = [random.randint(0,1000) for _ in range(10)]
def sort(nums):
if len(nums) < 2:
return nums
pivot = nums[0]
x, y = divide(pivot, nums[1:])
return sort(x) + [pivot] +sort(y)
def divide(pivot, nums):
if len(nums) < 1:
return ([], [])
x, y = divide(pivot, nums[1:])
num = nums[0]
if num < pivot:
return [num] + x, y
else:
return x, [num]+y
```

**Merge sort**: a type of Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The point is that the numbers are sorted just when the numbers are merged.

```
def sort(nums):
if len(nums) < 2:
return nums
center = len(nums) // 2
left = sort(nums[:center])
right = sort(nums[center:])
return merge(left, right)
def merge(left, right):
if len(left)<1:
return right
if len(right)<1:
return left
if left[0] > right[0]:
return [right[0]] + merge(left, right[1:])
else:
return [left[0]] + merge(left[1:], right)
```

**Search**: the algorithm to find the number which you want. There are three kinds of basic search algorithms such as linear search, binary search, and binary search with recursion. The input data of the below code is sorted in order.

```
# linear search
import random
target = 217
nums = [1, 103, 196, 217, 262, 420, 577, 630, 649, 908]
def linear_search(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
# binary search
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
center = (left + right) // 2
if nums[center] == target:
return center
elif nums[center] < target:
left = center +1
else:
right = center -1
# binary search with recursion
def binary_search(nums, target):
def _binary_search(nums, target, left, right):
if left > right:
return -1
center = (left + right) //2
if nums[center] == target:
return center
elif nums[center] < target:
return _binary_search(nums, target, center+1, right)
else:
return _binary_search(nums, target, 0, center-1)
return _binary_search(nums, target, 0, len(nums)-1)
```

**Stack**: a stack is an abstract data type that serves as a collection of elements, with two main principal operations:**push**, which adds an element to the collection, and**pop**, which removes the most recently added element that was not yet removed.

```
format1 = {"key1": "value1", "key2": [1,2,3], "key3":(1,2,3)}
format2 = "[]"
format3 = "[][[{}]]{"
# validate pair format
def validate_format(char):
lookup = {"{":"}", "[":"]", "(":")"}
stack = []
for c in char:
if c in lookup.keys():
stack.append(lookup[c])
if c in lookup.values():
if not stack:
return False
if c != stack.pop():
return False
if stack:
return False
return True
# reverse string
from collections import deque
sentence = 'gnirtS esreveR'
def reverse_str(sentence):
stack = deque(sentence)
return ''.join(stack.pop() for _ in range(len(sentence)))
reverse_str(sentence)
-> 'Reverse String'
```

**Queue**: a queue is open at both its ends. One end is always used to insert data (**enqueue**) and the other is used to remove data (**dequeue**).

```
from collections import deque
def reverse(queue):
new_queue = deque()
while queue:
new_queue.append(queue.pop())
return new_queue
q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
print(q)
q = reverse(q)
print(q)
-> deque([1, 2, 3, 4])
-> deque([4, 3, 2, 1])
```

＊ **deque** allows us to add and remove from both sides of queue. While List needs O(n) to add and remove by using insert() and pop(), deque has append(), appendleft(), pop(), and popleft() which are O(1).