迪三
0%

一.分冶算法

发表于 分类于 Valine：

原创 进阶算法概述

一.分冶算法

1.算法本质

  • 一个问题规模为N的问题可以分解为k个规模较小的问题，这些子问题相互独立且与原问题性质相同，求出子问题的解可以得到原问题的解。

2.算法步骤

  • 分解
  • 求解（子问题比原问题易求）
  • 合并

2.1 伪代码

  • 伪代码
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
分治法的伪代码：

  v divide_and_conquer(proplem p)
  {//n为问题规模

      if(|p|<n0)//n0为一阈值

      solve(p);

       else
       {

           divide p into smaller subproblem P1,P2,...Pk;

           for(i=1;i<=k;i++)
           {

               yi=divide_and_conquer(Pi);
               #可能用到递归
               return merge(y1,y2,...,yk);

           }

       }

   }

3.例题(python)

3.1求众数(一个数组中重复最多的数)

  • 思想

（1）快速排序

（2）求中位数,及其重数(重复数)

（3）计算出中位数的最左端和最右端的位置(如果有重复)，然后分割成2段数组

（4）中位数个数与左端数组个数比较，中<左 即最大众数可能存在左端，将左端再进行2段分割（递归）直到 中 > 左为止

  • 代码
1
2
3
4
5
6
7
8
9
10
def mode(l,r) #l,r两个参数分别代表数组两端，a是数组
    med = median(a,l,r) //寻找中位数
    split = (a,med,l,r,l1,r1)//分割数组
    if largest<(r1-l1+1):
        largest=r1-l1+1
        element=med;//element是众数
    if(l1-1>largest):
        mode(1,l1-1)
    if(r-r1>largest):
        mode(r1+1,r)

3.2 合并排序

  • 基本思想:
    将一组数分为两组数，分别对两组数进行排序，将合并好的子集合合并到排好序的集合中
1
2
3
4
5
6
7
8
9
10
11
void MergeSort(Type a[],int left,int right)
{
    if(left < right)
        {
            int i = (left + right)/2
        }
    MergeSort(a,left,i)
    MergeSort(a,i+1,right)
    Merge(a,b,left,i,right)//合并数组到b
    Copy(a,b,left,right)//复制回数组a
}

3.3 快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def Qsort(a,left,right):
    l = left
    r = right
    key = a[0]
    while(l<r):
        while(l<r && a[r]>=key):
            r = r-1
        a[l] = a[r]
        while(l<r && a[l]<=key):
            l = l+1
        a[r] = a[l]
    a[0]= key
    Qsort(a,left,l-1)
    Qsort(a,l+1,right)

Qsort(a,0,len(a-1))

3.4 重复元素排列问题

  • 思想

    n个元素的全排列减小的n-1个元素的全排列，直至减小的1个元素的排列，就不需要排列

其他

分治法所能解决的问题一般具有以下几个特征：

  1. 该问题的规模缩小到一定的程度就可以容易地解决

  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

  3. 利用该问题分解出的子问题的解可以合并为该问题的解；

  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

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

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

http://blog.jobbole.com/83944/