2.3.1 Algorithms Flashcards
2.3.1 A)
What are the two things to check when developing an algorthim
Time complexity and space complexity
2.3.1 A)
What is time complexity
How much time it takes to solve a problem.
2.3.1 A)
How is time complexity measured. and what does it show
notation called big o notation. it shows the efficently of the algortihm. shows uper limit of time taken relative to number of elements inputted.
2.3.1 A)
What are the big o notaions, their names and what they do
- o(1) - constant time - time take independant from # of inputs
- o(n) linear time - tt direction properitaoinal to number of elements inputted
- o(n^n or n*2) polynomail time - time takes to complete is proportional to element to the n^n or n^2
- o(2^n) - exponent time tt doubles w very item
- o (log n) logarhimic time - tt, inc at smalleer rate of elements ^
2.3.1 A)
big o notations best to worse
O(1), O(LOG N), O(N), O(2^N)/O(N^N), O(N!)
2.3.1 A)
Draw big o notation as a graph
check notes
2.3.1 A)
space complexity, whats the significance of it, how is it measured
amount of storage the algorithm takes, ^storage = ^ expensive, bigO(o(n)) notation
2.3.1 A)
What is an algorithm, what are the two main objectives
a series of steps that completesa task, main objectives is to complete the task and then to space asd time complexity.
2.3.1 A)
How to reduce space complexity
- preform all changes on orginal peiece of data
- reduce embedded loops
- reduce # of items you need to do operations on
2.3.1 B)
What are stacks and how do they work
stacks are first in last out (Filo) data structures often implemted as arrays
2.3.1 B)
How do stacks keep track of elemeted
a sugular pointed called top pointer
2.3.1 B)
Why is the top pointer initalised at -1
the top pointer is initalised at -1 bcos pointer at 0 would suggest somthing is in the list as arrays start at index values 0.
2.3.1 B)
What are the operations and names for a stack
operations - name
checks size - size()
checks if empty - isEmpty()
return top element - peek()
add to stack - push(element)
returm top element and remove - pop()
2.3.1 B)
What does size() do in a stack ?
returns # of elements returns value of top point +1 as first element is in 0.
2.3.1 B)
What does isEmpty() do in a stack ?
checks if pointer is at 0> aka -1
2.3.1 B)
What does peek() do in a stack ?
returns top w/o removing it check if it is empty first or will get an error
2.3.1 B)
What does push(element) do in a stack ?
new item passed through parameter then at position of top pointer
2.3.1 B)
What does pop() do in a stack ?
the element at the position of the top pointer is record before being removed. the top pointer is decremented by one before removed item is returned. Make sure stack isnt empty before attemping to pop or error.
2.3.1 E)
Binary seach in steps
1) calc midpoint
2) (ub + lb) /2
3) compare arry midpoint with value
4) if same, flag set to true
5) if mp < value, mp = lb + 1
6) if mp > value, mp = ub + 1
7) repeat
8) until lb >= ub
9) return flag found
2.3.1 E)
linear seach in steps
1) compare search item w/ first value
2) compare search item w/ next value
3) repeat until either
4) end of array
5) item is found
6) return the position
2.3.1 E)
insertion sort in steps
1) start at second item
2) compare current with first item in sorted list
3)if current item large move infron of other item
4) repeat until current is less then or equal to sorted
5) move all up one
6) insert current
7) repeat until done
