# CS代考 COMP90038 – cscodehelp代写

COMP90038
Algorithms and Complexity
Lecture 9: Decrease-and-Conquer-by-a-Constant (with thanks to Harald Søndergaard)

DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

2
Decrease-and-Conquer- by-a-Constant
In this approach, the size of the problem is reduced by some constant in each iteration of the algorithm.

A simple example is the following approach to

sorting: To sort an array of length n, just
1. sort the first n − 1 items, then
2. locate the cell that should hold the last item, shift all elements to its right to the right, and place the last element.

Sorting n items
A:
0123456
Sort first n-1 items
23
9
52
12
41
83
46

Sorting n items
A:
0123456
9
12
23
41
52
83
46

Sorting n items
A:
0123456
9
12
23
41
52
83
46

Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
83
46
6

Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
83
83
7

Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
83
83
8

Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
52
83
9

Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
52
83

Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
46
52
83

Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
46
52
83