算法设计与分析-----分治法（js实现）

分治法

特征

该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解;该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

能否利用分治法完全取决于问题是否具有这条特征,如果具备了前两条特征，而不具备第三条特征,则可以考虑贪心算法或动态规划。

伪代码

divide-and-conquer(P) if(|P|<= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances Pl,P....Pk; //分解问题 for(i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 returnmrrge....yk);//将各子问题的解合并为原问题的解

人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。

例子

求指定整型数组的最大值和最小值。

传统做法就是遍历一遍下来求出最大值和最小值，时间复杂度是O(n)。

function divide_conquer(arr,from,to){ if(to - from == 1){ return {"max":Math.max(arr[from],arr[to]),"min":Math.min(arr[from],arr[to])} }else if(to - from == 0){ return {"max":arr[from],"min":arr[to]} }else{ var middle = parseInt(from+(to-from)/2); var result1 = divide_conquer(arr,from,middle); var result2 = divide_conquer(arr,middle+1,to); var result = {}; if(result1["max"] > result2["max"]){ result["max"] = result1["max"]; }else{ result["max"] = result2["max"]; } if(result1["min"] > result2["min"]){ result["min"] = result2["min"]; }else{ result["min"] = result1["min"]; } return result; } } var arr = [34,5,6,7111,7,8,889,9]; console.log(divide_conquer(arr,0,arr.length-1));

二分搜索

给你一-个装有16个硬币的袋子。16个硬币中有一 个是伪造的,并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你 完成这一任务,将提供台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。

算法描述

将16个硬币分成A、B两半;将A放仪器的一边, B放另-边,如果A袋轻，则表明伪币在A ,解子问题A即可,否则,解 子问题B。

实例

给定已按升序排好序的n个元素a|0:n-1|，现要在这n个元素中找出特定元素x。

function BinarySearch(arr, target) { //先排序 arr.sort((a, b) => { return a - b }); // console.log(arr.sort((a, b) => { return a - b })) let left = 0; let right = arr.length - 1; //console.log(right) while (left <= right) { let mid = Math.floor(left + (right - left) / 2); // console.log(mid) if (arr[mid] > target) { right = mid - 1; // console.log(right) } else if (arr[mid] < target) { left = mid + 1; } else { return "该数在数组中"; } } return "该数不存在" } BinarySearch([3, 2, 1, 3, 4, 6, 7], 1); console.log(BinarySearch([3, 2, 1, 3, 4, 6, 7], 1))

快速排序

思路

快速排序基于分治思想

Divide :分割Alp…r]成为2个子集合(可以空) Alp…q- 1]和A[q+ 1…r] 使得A[p…q- 1|的每个元素都小于等于A[q],A[q + 1…r’]中的每个元素都大于等于A[q],索引q作为分割点。

Conquer :通过递归调用快速排序对A[p…q-1]和A[q +1…r]排序。

Combine :每个子集合排序完成之后,整个数组的排序也完成。

伪代码

template<class Type> void QuickSort (Type a], int p, int r) { if (p<r){ int q=Partition(a,p,r); //切分的过程 QuickSort (a,p,q-1); //对左半段排序 QuickSort (a,q+1,r); //对右半段排序 }

实例

// 快速排序 /* 思想:二分的操作，递归的思想，分成左右两个数组，比当前小的放左边，大的放右边，重复以上操作，当递归到剩下的长度为<=1 时间复杂度 O(nlog n) */ function quick(arr){ // 结束递归 if(arr.length<=1){ return arr; } // 找到数组的中间向，在原有的数组中把他移除 let mid = Math.floor(arr.length/2); let midvalue = arr.splice(mid,1)[0]; // 准备左右两个数组，循环剩下数组中的每一项，比当前小的放左边，大的放右边 let arrright = [], arrleft = []; for(let i = 0;i<arr.length;i++){ let items= arr[i]; items <midvalue?arrleft.push(items):arrright.push(items) } // 递归方式让左右两边都排好序 return quick(arrleft).concat(midvalue,quick(arrright)); } quick([23,54,67,57,87,798,56,1,2,4])

快排的进一步思考

快速排序算法的性能取决于划分的对称性。通过修改算法partition ,可以设计出采用随机选择策略的快速排序算法。

伪代码

template<class Type> int RandomizedPartition (Type a[], int p, int r) { int i = Random(p,r); //随机选择划分基准 Swap(a[i], a[p]); return Partition(a, p, r); }

归并排序

算法描述

若n为1 ,算法终止;否则,将这一元素集合分割成两个或更多个子集合,对每- -个子集合分别排序然后将排好序的子集合归并为一个集合。

实例

function mergeSort(arr) { const length = arr.length; if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1 return arr; } const mid = Math.floor(length / 2); //分成左右两个部分 const left = arr.slice(0, mid); const right = arr.slice(mid, length); return merge(mergeSort(left), mergeSort(right)); //要将原始数组分割直至只有一个元素时，才开始归并 } function merge(left, right) { const result = []; let il = 0; let ir = 0; //left, right本身肯定都是从小到大排好序的 while( il < left.length && ir < right.length) { if (left[il] < right[ir]) { result.push(left[il]); il++; } else { result.push(right[ir]); ir++; } } //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可 while (il < left.length) { result.push(left[il]); il++; } while(ir < right.length) { result.push(right[ir]); ir++; } return result; } console.log(mergeSort([2,9,1,8,3,]))

覆盖残缺棋盘

伪代码

void chessBoard(int tr, int tc, int dr, int dc, int size) if (size == 1) return; intt= tile++, //L型骨牌号 s= size/2; //分割棋盘 //覆盖左上角子棋盘 if(dr<tr+ s&&dc<tc+ s) //特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else{l1此棋盘中无特殊方格 //用t号L型骨牌覆盖右下角 board[tr+ S- 1][tC+ s- 1]=t; //覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} //覆盖右上角子棋盘 if(dr<tr+ s&&dc>=tc+ s) /1特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {//此棋盘中无特殊方格 //用t号L型骨牌覆盖左下角 board[tr +s- 1][tc+ s]=t; //覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} //覆盖左下角子棋盘 if (dr>=tr+ s&&dc<tc+ s) //特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else {//用t号L型骨牌覆盖右上角 board[tr + s][tc+ S- 1]= t; //覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s);} //覆盖右下角子棋盘 if(dr>=tr+ s&& dc>=tc+ s) //特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else {//用t号L型骨牌覆盖左上角 board[tr + s][tC+ s]=t; //覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s);} }

复杂度分析

复杂度分析 0(1)k=0 T(k)= 4T(k-l)+O(1) k>0

​ T(n)=O(4k) 渐进意义下的最优算法