Python Flashcards
(193 cards)
Example O(log n)
Binary search
Example O(n)
- Simple search
Example O(n * log n)
quicksort (fast)
Example O(n2)
- selection sort (slow)
actually O(n × 1/2 × n) list get's smaller each time you find an element
O(n!)
traveling salesperson
Explain O(n)
Big O and n = number of operations
time factor would be c*O(n)
Average cost for execution
binary search algo
- sorted list (!)
- calc mid point
- == return pos
- list[mid]> item -> high=mid-1
- list[mid]< item -> low=mid+1
def binary_search(list, item):
low = 0
high = len(list)-1
while low <= high:
delta=(high-low)//2
mid = low+delta
if list[mid] == item:
return mid
if list[mid] > item:
high = mid - 1
else:
low = mid + 1
return low
log 8
3: 23
log 1,024
10: 210
log 256
- 8: 28
Big O of reading array
O(1)
a[5]
Big O of reading linked list
O(n)
Big O of inserting array
O(n)
array with 4 elements and you add another requires new array and moving elements over
Big O of inserting linked list
O(1)
Minimal implementation of linked list
class Node: def \_\_init\_\_(self, **val=None**): self.val = val # the value self.next = None # reference to next node
find smallest element in array
def findSmallestIndex(arr): smallest\_index = 0 for i in range(1, len(arr)): if arr[i] \< arr[smallest\_index]: smallest\_index = i return smallest\_index
Selection sort
def selectionSort(arr): n=len(arr) for i in range(n): nmin=arr[i] npos=i for j in range(i+1,n): if arr[j]: **nmin=arr[j]** **npos=j** arr[npos]=arr[i] arr[i]=nmin
in-place sorting
Remove element from array\list
and return the value
- val=array.pop(index)
- from end arr.pop()
- from start arr.pop(0)
Count down using recursion
def countdown(i): print(i)
base case
if i <= 0:
return
else:
# recursion
countdown(i-1)
Runtime O(n)
Explain call stack
stack:
push new item on top
pop from the top most item
When you call a function from another function, the calling function is paused in a partially completed state.
Applies to recusrsion.
Library to import type List?
from typing import List
others:
from typing import Mapping, Optional, Sequence, Union
Library to import Optional?
- from typing import Optional
Get Maximum, Minimum
max() and min() no import required
Mutable vs immutable
mutable = liable to change
Everything in Python is an Object, every variable holds an object instance.
Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable.





















