算法概述

什么是算法

什么是算法?笼统的地说,算法是求解一类问题的任意一种特殊的方法。较严格的说法是,一个算法是对特定问题求解步骤的一种描述,它是指令令的有限序列。大白话解释:根据一定的条件，对一些数据进行计算，得到需要的结果。

算法具有以下5个特征:

  1. 输入:算法有零个或多个输入量
  2. 输出: 算法至少产生一个输出量
  3. 确定性: 算法的每一条指令都有确切的定义, 没有二义性
  4. 能行性:算法的每一条指令必须足够基本,它们可以通过已经实现的基本运算执行有限次来实现
  5. 有限性:算法必须总能在执行有限不之后终止

用生活中的例子来说明算法:例如从常德到北京，如何去？会有不同的解决方案，我们可以坐飞机，可以坐火车，可以坐汽车，甚至可以步行，不同的解决方案带来的时间成本和金钱成本是不一样的，比如坐飞机用的时间最少，但是费用最高，步行费用最低，但时间最长。

在程序中，我们也可以用不同的算法解决相同的问题，而不同的算法的成本也是不相同的。总体上，一个优秀的算法追求以下两个目标：

  1. 花最少的时间完成需求
  2. 占用最少的内存空间完成需求；

算法实例

时间复杂度分析

需求一、计算1到100的和

方法一、

1
2
3
4
5
6
7
8
public static void main(String[] args){
    int sum = 0;
    int n = 100;
    for(int i=1;i<=n;i++){
        sum+=i;
    }
    System.out.println("sum=" + sum);
}

方法二、

1
2
3
4
5
6
public static void main(String[] args) { 
    int sum = 0; 
    int n= 100; 
    sum = (n+1)*n/2; 
    System.out.println("sum="+sum); 
}

分析:

第一种解法要完成需求，要完成以下几个动作：

  1. 定义两个整型变量；

  2. 执行100次加法运算；

  3. 打印结果到控制台；

第二种解法要完成需求，要完成以下几个动作：

  1. 定义两个整型变量；

  2. 执行1次加法运算，1次乘法运算，一次除法运算，总共3次运算；

  3. 打印结果到控制台；

很明显，第二种算法完成需求，花费的时间更少一些。

空间复杂度分析

需求二、计算10的阶乘

方法一、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test { 
    public static void main(String[] args) { 
        //测试，计算10的阶乘 
        long result = fun1(10); 
        System.out.println(result); 
   }
       //计算n的阶乘 
    public static long fun1(long n){ 
        if (n==1){ 
            return 1; 
        }
        return n*fun1(n-1); 
        } 
}

方法二、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test { 
    public static void main(String[] args) { 
        //测试，计算10的阶乘 
        long result = fun2(10); 
        System.out.println(result); 
    }
    //计算n的阶乘 
    public static long fun2(long n){ 
        int result=1; 
        for (long i = 1; i <= n; i++) { 
            result*=i; 
        }return result; 
    } 
}

第一种解法，使用递归完成需求，fun1方法会执行10次，并且第一次执行未完毕，调用第二次执行，第二次执行未完毕，调用第三次执行…最终，最多的时候，需要在栈内存同时开辟10块内存分别执行10个fun1方法。

第二种解法，使用for循环完成需求，fun2方法只会执行一次，最终，只需要在栈内存开辟一块内存执行fun2方法即可。

很明显，第二种算法完成需求，占用的内存空间更小。

分治算法

分治算法介绍

基本概念

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

解题思路

1、原问题可以分解为多个子问题
这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
2、原问题在分解过程中，递归地求解子问题
由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
3、在求解并得到各个子问题的解后
应能够采用某种方式、方法合并或构造出原问题的解。
不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想 。

分治算法应用分析

先让我们通过一个简单的二分查找来理解分治算法的基本思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int commonBinarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;         //定义middle
        
        if(key < arr[low] || key > arr[high] || low > high){
            return -1;              
        }
        
        while(low <= high){
            middle = (low + high) / 2;
            if(arr[middle] > key){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(arr[middle] < key){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return middle;
            }
        }
        
        return -1;      //最后仍然没有找到，则返回-1
    }

首先先在排序的数组找到中间值，定义我们的中间值，找到就返回，找不到就在符合条件的子问题继续二分，直到满足边界条件退出循环。

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.

img

img

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
public static int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }
     
    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i= low;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }