Mind map
Decrease and conquer
Map content
Decrease and conquer
- Reduce problem instance to smaller instance of the same problem - Solve smaller instance - Extend solution of smaller instance to obtain solution to original instance - Can be implemented either top-down or bottom-up - Also referred to as inductive or incremental approach ----------------------------------------
Decrease by a constant (usually by 1)
- ex: aˆn reduce it to aˆn-1
- insertion sort
- Sort 6, 4, 1, 8, 5 6 | 4 1 8 5 start by 6 4 6 | 1 8 5 then compare 4 1 4 6 | 8 5 1 4 6 8 | 5 1 4 5 6 8
- topological
Decrease by factor
- decrease by half,third .... ex:3ˆ8 = 3ˆ4*3ˆ4
Decrease by variable size
Information
- Description
- Mind Map on Decrease and conquer, created by Ghezala Mohamed on 19/10/2018.
- Created by
- Ghezala Mohamed
- Views
- 0
- Rating