本文主要是介绍分治法（逆序数 大数乘法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
例子:
An old puzzle: We are given 27 coins of the same denomination; we know that one of them is counterfeit and that it is lighter than the others. Find the counterfeit coin by weighing coins on a pan balance only three times.Solution:This method is called "divide-and-conquer"We have already seen a prototypical "serious" algorithm designed using such a method: the merge sortwe split the array into two,sort the two parts recursively and then merge the two sorted arrays.
设计思路:
对于一个规模为n的问题 若该问题可以容易的解决则直接解决
否则将其分解成k个规模较小的子问题
这些子问题互相独立 且与 原问题形式相同
递归地解决这些子问题
然后将各子问题的解合并得到原问题的解
使用情况
该问题的规模缩小到一定的程度就可以很容易的解决该问题可以分解为若干个规模较小的相同问题 即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的即子问题之间不包含公共的子子问题
基本步骤
1.分解：分解成若干规模小 相互独立 与原问题形式相同的子问题
2.解决：直接解决或者递归求解
3.合并：合并各子问题的解来得到原问题的解
例子
计算逆序对
逆序对： if i < j && a[i] > a[j] 就是一个逆序对arr: 1 11 9 12 7 10 3 4 6 8 2 5brute force: O(n^2)
divide&conquer:
步骤:1.分解先进行对半划分 直到最后左半边数组只有一个元素 右半边数组中也只有一个元素 此时开始进行回溯合并。2.合并在回溯过程中 左半边和右半边元素都是升序排列 当发现左边元素大于右边元素时，那么左半边这个元素及其后面的所有元素均大于这个右半边的元素 记这些元素的个数为len 那么逆序对的个数要自增 mid - left + 13. 代码(merge sort + count)import java.util.Arrays;public class DivideAndConquer {public static int conquer(int []nums,int left,int mid,int right) {int[] tmp = new int[right-left+1];int i = 0;int l = left;int m = mid+1;int count = 0;while( l <= mid && m <= right ) {if( nums[l] < nums[m] ) {tmp[i++] = nums[l++];}else {tmp[i++] = nums[m++];count += mid - l + 1;}}while( l <= mid ) {tmp[i++] = nums[l++];}while( m <= right ) {tmp[i++] = nums[m++];}for(int s = 0; s <= (right-left) ;s++) {nums[left+s] = tmp[s];}return count;}public static int divide(int[] nums,int left,int right) {int mid = (left+right)/2;int count = 0;if(left < right) {count += divide(nums, left, mid);count += divide(nums, mid+1, right);count += conquer(nums,left,mid,right);System.out.println( Arrays.toString(nums)+" "+count );}return count;
}public static void main(String[] args) {int[] nums = {10,2,0,12,5,3};divide(nums, 0, nums.length-1);}
}
分治法的时间复杂度:
假设：有一个规模为n的问题 时间函数为T(n)分成k个问题 每个问题的规模为n/m, 则每个子问题的时间函数为T(n/m)最小子问题为n=1，解规模为1的问题时需耗费1个单位时间。将子问题的解合并为原问题的解需要f(n)=n的d次方 个时间单位O(1) n = 1T(n)= {K*T(n/m) + f(n) n>1
大数乘法
先看看大数加法:int、float、double等基本数据类型的数据容量有限，不深究它们的具体范围是多大，但粗略估算，大概也不超过25位吧。如果有一个是50位的数字，基本数据类型根本无法存储这么大的数字，那我们应该怎么办？这时候，我们应该采用大数的思想:用数组来分别保存这50位数字中各个位的数字。大数加法的时间复杂度是 O(n) n位数对应相加
大数乘法是进行n次 加法运算 所以时间复杂度是 O(n^2)
用分治法进行优化:分治法的算法是A*B=a1*b1*10^n+[(a1+a0)*(b0+b1)-a1*a0-b1*b0]*10^n/2+a0*b0对于这个算法的时间复杂度，我们需要做3次n/2级别的乘法。即T(n)=3*T(n/2)+O(n),时间复杂度是T(n) = O(n^log2(3) ) = O(n^1.59 ).
我们假设要相乘的两个数是x * y。我们可以把x，y写成：x=a∗10n/2+by=c∗10n/2+dA * B = c2 * 10^n + c1 * 10^(n/2) + c0其中：c2 = a1 * b1c1 = a0 * b1 + b0 * a1 = (a1 + a0) * (b1 + b0) - (c2 + c0)
这篇关于分治法（逆序数 大数乘法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
