Peak detection by Improved Divide & Conquer on 2D and 3D arrays
More information about Improved Divide & Conquer [page 5] : Peak Finding 1D and 2D
For algorithm analysis and more details, take a look at doc
1- Find middle row/column, then pick a number in middle row/column => O(1)
2- Check if the number is peak number, if it is a peak number then return it => O(1)
3- Find max number in row/column => O(m) or O(n)
4- Check if the number is peak number, if it is a peak number then return it => O(1)
5- Compare max number with its neighbors => O(1)
- If the max’s neighbor is bigger than max, then maintain search on neighbor’s part => O(1)
arr[midRow+1][max] > arr[midRow][max]
arr[max][midCol+1] > arr[max][midCol]
- If the max’s other neighbor is bigger, then maintain search on this neigbor’s part => O(1)
arr[midRow-1][max] > arr[midRow][max]
arr[max][midCol-1] > arr[max][midCol]
Improved Divide & Conquer 2D Runtime Chart
n (number of rows) | m (number of columns) | rowOrCol | Time(ns) |
---|---|---|---|
10 | 100 | 0 | 13800 |
10 | 100 | 1 | 12500 |
10 | 100 | 2 | 3900 |
100 | 10 | 0 | 11800 |
100 | 10 | 1 | 15100 |
100 | 10 | 2 | 9100 |
50 | 200 | 0 | 197599 |
50 | 200 | 1 | 151499 |
50 | 200 | 2 | 85700 |
200 | 50 | 0 | 245500 |
200 | 50 | 1 | 37600 |
200 | 50 | 2 | 474699 |
50 | 1000 | 0 | 219700 |
50 | 1000 | 1 | 158200 |
50 | 1000 | 2 | 449800 |
1000 | 50 | 0 | 241600 |
1000 | 50 | 1 | 135099 |
1000 | 50 | 2 | 78700 |
50 | 10000 | 0 | 1661400 |
50 | 10000 | 1 | 126201 |
50 | 10000 | 2 | 680400 |
10000 | 50 | 0 | 230900 |
10000 | 50 | 1 | 143999 |
10000 | 50 | 2 | 1238900 |
Condition 1 : rowOrCol = 0 ---> array is split by rows
Condition 2 : rowOrCol = 1 ---> array is split by columns
Condition 3 : rowOrCol = 2 ---> first, array is split by rows then columns
1- Find middle layer, then pick a number in midLayer => O(1)
2- Check if the number is peak number, if it is a peak number then return it => O(1)
3- Find max number in midLayer => O(mn)
4- Check if the number is peak number, if it is a peak number then return it => O(1)
5- 5- Compare max number with its neighbors => O(1)
- If the max’s neighbor is bigger than max, then maintain search on neighbor’s part => O(1)
arr[max][max][midLayer] > arr[max][max][midLayer+1]
- If the max’s other neighbor is bigger, then maintain search on this neighbor’s part => O(1)
arr[max][max][midLayer] > arr[max][max][midLayer-1]