小撒是一只好學(xué)的小鴨子萍嬉,這天嚎朽,小撒在學(xué)習(xí)算法
分治法
分治法(divide-and-conquer)是一種算法設(shè)計(jì)策略蜗侈。使用分治法的算法在每一層迭代有3個(gè)步驟:
- 分解(divide):將原問(wèn)題分解成一系列子問(wèn)題
- 解決(conquer):遞歸解決子問(wèn)題鲤拿;在子問(wèn)題足夠小時(shí)蚂四,直接解決子問(wèn)題
- 合并(combine):將子問(wèn)題的結(jié)果合并為原問(wèn)題的解
合并排序
合并排序(merge sort)便是使用了分治的策略沥阳。
如果我們有兩個(gè)已經(jīng)排序好的數(shù)組跨琳,要得到兩者合并后的排序數(shù)組,我們只需反復(fù)比較兩個(gè)數(shù)組頭部(最谢ο)的元素湾宙,將更小的取出并放入結(jié)果數(shù)組:
合并排序圖示
我們可以不斷的將規(guī)模為n
的問(wèn)題分解為規(guī)模為n / 2
的問(wèn)題,直至n/2 <= 1
:
合并排序的時(shí)間復(fù)雜度
遞歸樹(shù)(recursion tree)每向下一層冈绊,規(guī)模為n
的問(wèn)題T(n)
被分解為兩個(gè)T(n/2)
的問(wèn)題侠鳄,因此樹(shù)的總高度為ln(n)/ln(2)
。
而合并兩個(gè)T(n/2)
死宣,則共需要n
次比較并取出較小值伟恶,因此每層的總操作數(shù)為n
,由此得到合并排序的時(shí)間復(fù)雜度為θ(n * log(n))
毅该。
代碼示例(js)
const merge = (arr, start, mid, end) => {
const arr1 = arr.slice(start, mid + 1)
const arr2 = arr.slice(mid + 1, end + 1)
while (end >= start) {
if (arr2.length === 0) {
arr[start] = arr1.shift()
} else if (arr1[0] < arr2[0]) {
arr[start] = arr1.shift()
} else {
arr[start] = arr2.shift()
}
start++
}
}
const mergeSort = (arr, start, end) => {
if (end > start) {
const mid = Math.floor((end + start) / 2)
mergeSort(arr, start, mid)
mergeSort(arr, mid + 1, end)
merge(arr, start, mid, end)
}
}
小結(jié)
合并排序使用了分治的算法策略博秫,相比插入排序等算法大大提高了時(shí)間復(fù)雜度潦牛,但也引入了O(n)
的空間成本。