2.3.1 Algorithms
暂无描述。系统推荐的高质量记忆内容，适合每天坚持背诵学习。
卡片预览 (24 张)
Algorithms
A series of instructions that are used to solve a problem
Properties of a good algorithm
• Produce the correct output for valid inputs • Should account for invalid inputs • Must always terminate at some point • Executes efficiently in as few steps as possible • Should be designed such that other people can easily understand and modify it
Big O notation
The time complexity of an algorithm, how changing the size of the units affects the runtime Remove coefficients and write the highest power of n only
Big O process
• Calculate how many times each line runs • Simplify • Remove coefficients and put O(n^highest power)
Sequential big O
O(1)
Single loop big O
O(n)
Loops inside each other big O
O(n^2)
Recursive functions big O
O(numberofrecursions^n)
Divide and conquer big O
O(log n)
Permutations
The permutation of n items is the number of ways n items should be arranged
Permutation where values can be repeated big O
O(a^n) Where a is the amount of possible values for each
Permutation where values can’t be repeated big O
O(n!)
Linear search
Iterates through each item in turn until you find the item or have checked every item
Linear search pseudocode
Iterating through an array until the value is found, at which point the index is returned or if the loop is completed the value has not been found
Linear search big O
O(n)
Binary search big O
O(log n)
Binary search process
Order the items and examine the middle item of the list. if that is the item it is found, else repeat using the items bigger or smaller than the value depending if it is bigger or smaller than the middle value
Binary search pseudocode
The lowerbound starts at 0 and the upperbound 1 less than the list length The midpoint is (LB + UB) DIV 2 If the midpoint is the value return the index If the midpoint is less than the value LB is midpoint + 1 If the midpoint is more than the value UB is midpoint - 1 If lowerbound > upperbound it is not found
Bubble sort big O
O(n^2)
Insertion sort big O
O(n^2)
Bubble sort pseudocode
for (i = 0 to length - 2) for (j = 0 to length - i - 1) if list[i] > list [i + 1] temp = list[i] list[i] = list[i + 1] list [i + 1] = temp end if next j next i end procedure
Insertion sort pseudocode
for (j = 1 to length - 1) nextItem = list[j] i = j - 1 while i>=0 and list[i] > nextItem list [i+1] = list[i] i-- end while list{i+1] = nextItem next j end procedure
Merge Sort Process
• Divide the unsorted list into n sublists, each containing one element, halving the length each time • Order consecutive pairs of sublists and combine • Repeat to have 4 items in each ordered list • Repeat until there is one ordered list
Merge Sort Big O
n log n