Karteikarten
Week 6: Brute Force & Computational Complexity
Karten in diesem Stapel (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)
Informationen
- Beschreibung
- Computer Science (FIT1045: Algorithms & Programming Fundamentals in Python) Karteikarten am Week 6: Brute Force & Computational Complexity, erstellt von Melina Mackey am 16/09/2019.
- Erstellt von
- Melina Mackey · Sep 2019
- Aktualisiert
- 21 Sep 2019
- Aufrufe
- 0
- Verlauf
-
- Erstellt von Melina Mackey · 2 Sep 2019
- Kopiert von Melina Mackey · 2 Sep 2019
- Kopiert von Melina Mackey · 2 Sep 2019
- Kopiert von Melina Mackey · 2 Sep 2019
- Kopiert von Melina Mackey · 16 Sep 2019
- Bewertung