Flashcards
Week 6: Brute Force & Computational Complexity
Cards in this deck (12)
- 1Brute force approach1. Generate all the solutions candidates
2. Filter for feasible solutions
3. Return the optimal remaining solution - 2Lexicographic orderAllows systematic enumeration of each solution
- 3Bitlists- Candidate solutions are a combination of values from a set (i.e. a subset)
- In general, the number of different subsets we can form from n items is 2n
- Each item has 2 possibilities: either selected (1) or not (0)
- E.g. Knapsack problem - 4Bitlists: lexicographic successorIterate over the list from right to left:
1. If a 1 is encountered, change it to 0 and continue
2. If a 0 is encountered, change it to 1 and return the list - 5Bitlists algorithm
- 6Permutations- Candidate solutions are an arrangement of items
- No need to filter for feasible solutions
- E.g. Travelling salesman problem (TSP)
- 7Permutations algorithm
- 8Permutations: lexicographic successor
- 9Computational (time) complexity of an algorithmRunning time of a program depends on:
1. Machine used to execute the program
2. Input (larger inputs take longer)
3. Computational complexity of the algorithm => number of elementary steps T(n) needed to compute output for an input of size n - 10Asymptotic analysis (Big-O notation)Constant terms and coefficients of are negligible compared to order of growth
- 11Selection sort complexity- Quadratic worst-case complexity
- Asymptotically no difference between best and worst-case
- Overall complexity is determined by step of highest complexity
- 12Insertion sort complexity- Quadratic worst-case complexity
- Linear best-case complexity (adaptive)
Information
- Description
- Computer Science (FIT1045: Algorithms & Programming Fundamentals in Python) Flashcards on Week 6: Brute Force & Computational Complexity, created by Melina Mackey on 16/09/2019.
- Created by
- Melina Mackey · Sep 2019
- Updated
- Sep 21, 2019
- Views
- 0
- History
-
- Created by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 16, 2019
- Rating