Fichas
Week 6: Brute Force & Computational Complexity
Fichas del conjunto (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)
Información
- Descripción
- (FIT1045: Algorithms & Programming Fundamentals in Python) Computer Science Fichas sobre Week 6: Brute Force & Computational Complexity, creado por Melina Mackey el 16/09/2019.
- Creado por
- Melina Mackey · sep 2019
- Actualizado
- 21 sep 2019
- Visitas
- 0
- Historial
-
- Creado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 16 sep 2019
- Valoración