- ALGORITHMS //
- DATA STRUCTURES //
-
Arrays, Sets
- Time Complexity
- Hash Tables
- Stacks
- Queues
- Linked Lists
- Trees
- Binary Search Trees
- Tries
- Graphs
Reading / 1 step
A computer can jump to any memory address in one step.
data = ['apples', 'bananas', 'oranges']
item = data[index] # Reading takes 1 step
print('Found item =', item)
print("Steps =", 1)
"""
Found item = bananas
Steps = 1
"""
Searching / N steps
For N cells in an array, linear search would take a maximum of N steps.
def search_value(arr, value):
steps = 0
for i in range(len(arr)):
steps += 1
if value == arr[i]:
return i, steps
return -1, steps
data = ['apples', 'bananas', 'oranges']
key, steps = search_value(data, 'oranges')
print('Found at index =', key)
print('N =', len(data))
print('Steps =', steps)
"""
Found at index = 2
N = 3
Steps = 3
"""
Insertion / N+1 steps
We need to shift items in order to make room for the new item.
def add_item(data, new_value, key):
data.append('') # add element at the end of array
steps = 0
for i in range(len(data), key+1, -1): # shift the elements to the right
data[i-1] = data[i-2]
steps += 1
print(data)
data[key] = new_value
steps += 1
return steps
data = ['apples', 'bananas', 'oranges']
print(data)
size = len(data)
steps = add_item(data, 'cherries', 0)
print(data)
print('N =', size)
print('Steps =', steps)
"""
['apples', 'bananas', 'oranges']
['apples', 'apples', 'bananas', 'oranges']
['cherries', 'apples', 'bananas', 'oranges']
N = 3
Steps = 4
"""
Deletion / N+1 steps
To delete an item require one step, then N-1 step for shifting the rest of elements.
def delete_item(data, key):
steps = 0
for i in range(key, len(data)-1): # shift elements to left (down to key)
data[i] = data[i+1]
steps += 1
data.pop() # remove last element
steps += 1
return steps
data = ['apples', 'bananas', 'oranges']
size = len(data)
steps = delete_item(data, 0)
print(data)
print('N =', size)
print('Steps =', steps)
"""
['bananas', 'oranges']
N = 3
Steps = 3
"""
Set / Insertion
A set is a data structure of unordered elements that doesn't allow duplicates. In terms of time compexity, the only difference between arrays and sets is at insertion.
def add_item(data, new_value):
steps = 0
# Check for duplicates
for item in data:
steps += 1
if item == new_value:
return -1
# Add new value to the set (random location in the set)
data.add(new_value)
steps += 1
return steps
data = {'apples', 'bananas', 'oranges', 'cherries'}
steps = add_item(data, 'mangos')
print(data)
print('Steps =', steps, '\n')
"""
{'oranges', 'mangos', 'bananas', 'apples', 'cherries'}
Steps = 5
"""
Ordered / Binary Search
When inserting we need to make a search before in order to get the correct spot. While insertion is less efficient for an ordered array, the search is match more efficient.
def binary_seach(arr, val):
left = 0
right = len(arr) - 1
steps = 0
while True:
steps += 1
middle = (left + right) // 2
if val == arr[middle]:
return middle, steps
if val > arr[middle]:
left = middle + 1
if val < arr[middle]:
right = middle - 1
if left > right:
return -1, steps
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
key, steps = binary_seach(data, 7)
print("Found:", key, end=' ')
print("Steps =", steps)
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
key, steps = binary_seach(data, 17)
print("Found:", key, end=' ')
print("Steps =", steps)
data = [i for i in range(0, 100_100)]
key, steps = binary_seach(data, 70_000)
print("Found:", key, end=' ')
print("Steps =", steps)
"""
Found: 6 Steps = 4
Found: 16 Steps = 5
Found: 70000 Steps = 16
"""
Last update: 303 days ago
