分治思想

文章目录
  1. 1. 分治思想
  2. 2. 可以解决的问题

记录分治思想

分治思想

分治,分而治之。分治是一种处理问题的思想,递归是一种编程技巧。

步骤:

  1. 分解:将源问题分解成一系列子问题
  2. 解决:递归的求解各个子问题,若子问题足够小,直接求解
  3. 合并:将子问题的结果合并成源问题

满足的条件:

  1. 原问题与分解的小问题具有相同的模式
  2. 原问题分解的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法和动态规划的明显区别
  3. 具有分解终止条件,也就是说,当问题足够小时,可以直接求解
  4. 可以将子问题合并成原问题,而这个合并操作的复杂度不能太高

下面是分治求解逆序度的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Division {
var num = 0
func count(a: inout [Int], count: Int) -> Int {
num = 0
mergeSortCounting(a: &a, p: 0, r: count - 1 )
return num
}

func mergeSortCounting(a: inout [Int], p: Int, r: Int) {
if p >= r {
return
}

let q = (p + r) / 2
mergeSortCounting(a: &a, p: p, r: q)
mergeSortCounting(a: &a, p: q+1, r: r)
merge(a: &a, p: p, q: q, r: r)
}

func merge(a: inout [Int], p: Int, q: Int, r: Int) {
var i = p
var j = q + 1
var k = 0

var temp: [Int] = Array(repeating: 0, count: r-p+1)

while i <= q && j <= r {
if a[i] <= a[j] {
temp[k] = a[i]
i += 1
} else {
num += (q - i + 1)
temp[k] = a[j]
j += 1
}
k += 1
}

while i <= q {
temp[k] = a[i]
i += 1
k += 1
}

while j <= r {
temp[k] = a[j]
j += 1
k += 1
}

for i in 0 ... r-p {
a[p+i] = temp[i]
}
}

static func testDivision() {
var a = [2,4,3,1,5,6]
let division = Division()
print(division.count(a: &a, count: 6))
}
}

可以解决的问题

分治可以解决耗时问题、大内存问题。