Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
2.3.1 a
| Question | Answer |
|---|---|
| Systemic approach to problem–solving | reaching a solution by identifying the individual steps required; by creating a set or rules, an algorithm that is followed precisely will lead to an answer |
| Systemic approach to problem–solving steps | 1. Break the problem down 2. Use abstraction 3. Consider relevant data structures 4. Tackle each part of the program step by step |
| Comparing Different Algorithms | ALWAYS USE WORST-TIME WHEN COMPARING (but also need to know best + average) |
| Bubble sort time complexity | Best: O(n) Average: O(n^2) Worst: O(n^2) |
| Bubble sort space complexity | O(1) |
| Insertion sort time complexity | Best: O(n) Average: O(n^2) Worst: O(n^2) |
| Insertion sort space complexity | O(1) |
| Merge sort time complexity | Best: O(n log n) Average: O(n log n) Worst: O(n log n) |
| Merge sort space complexity | O(n) |
| Quicksort time complexity | Best: O(n log n) Average: O(n log n) Worst: O(n^2) |
| Quicksort space complexity | O(log n) |
| Linear search/serial search time complexity | Best: O(1) Average: O(n) Worst: O(n) |
| Binary search time complexity (array) | Best: O(1) Average: O(logn) Worst: O(logn) |
| Binary search time complexity (binary search tree) | Best: O(1) Average: O(logn) Worst: O(n) |
| Hashing (search) time complexity | Best: O(1) Average: O(1) Worst: O(n) |
| Breadth/depth first search time complexity | Best: O(1) Average: O(V+E) Vertices + Edges O(V^2) |
| Adding items to structures | O(1) |
| Generating hash value | O(1) (in overflow) O(n) |
| Binary tree (searching/inserting) | O(log n) |
| Binary tree (traversing) | O(n) |
| Time complexity | how long it takes to run |
| Space complexity | how much storage is taken up |
| Big O notation | expresses the time or space complexity, although we will be talking about time on this page. It always assumes the worst-case scenario |
| Big O notation rules | Remove all terms except the one with the largest factor or exponent Remove any constants |
| If a program has complexity 5+3n+1, then | 5+3n+1 turns to 3n 3n turns to n (which you then surround by O, leading to O(n)) |
| If a program overall is O(1)+O(n)+O(n2), then | O(1)+O(n)+O(n2) turns to O(n2) |
| Classifications in Big O notation | (good to bad) 1. Constant 2. Logarithmatic 3. Linear 4. Polynomial 5. Exponential |
| Constant (big o notation) | O(1) Always executes in the same amount of time No loops |
| Logarithmatic (big o notation) | O(log n) Halves the data set in each pass (opposite to exponential) Halving a data set |
| Linear (big o notation) | O(n) Performance declines as the data set grows For/while loop |
| Polynomial (big o notation) | O(n^2) Performance is proportional to the square of the size of the data set Nested loops (if 2 loops, then square n, if 3 cube it and so on) |
| Exponential (big o notation) | O(2^n) Doubles with each addition to the data set in each pass (opposite to logarithmic) Recursive (calls itself twice) |
Created by:
FlashCardFun!