2.算法分析

2022-07-18

2.算法分析

算法(algorithm) 是为求解一个问题需要遵循的,被清除指定的简单指令的集合

运行时间计算的一般法则

  1. for循环

    1个for循环的运行时间至多是该for循环内部那些语句(包含测试)的运行时间乘以迭代的次数

  2. 嵌套的for循环

    从里向外分析这些循环,在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积

  3. 顺序语句

    将各个语句的运行时间求和即可(这意味着,其中的最大值就是所得的运行时间)

  4. if/else语句

    一个if/else语句的运行时间从不超过判断的运行时间再加上S1和S2中运行时间长者的总的运行时间

  5. 递归需要具体分析

斐波那契数列(3/2)的N次方<=fib(n)<(5/3)的N次方

最大子序列和问题的求解

  1. 算法1:穷举式地尝试所有可能的结果

    public static int maxSubSum(int [] a) {
    int maxSum = 0;
    /*

    • i控制从哪里开始加,0时从-2开始加,1时从11开始加
    • j控制加到哪里结束,i=0,j=0时加到-2,i=0,j=1时加到11
    • k控制每个加数的下标,例如i=2,j=4时,2<=k<=4,thisSum = -4+13+-5
      */
      for(int i = 0;i<a.length;i++) {
      for(int j = i;j < a.length;j++) {
      int thisSum = 0;
      for(int k = i;k <= j;k++) {
      thisSum += a[k];
      }
      //这里的if语句写到第二层循环和第三层循环区别很大,写到二层时O(N平方),
      //写到3层是O(N三次方),对于运行时间的影响很大
      if(thisSum > maxSum) {
      maxSum = thisSum;
      }
      }
      }
      return maxSum;
      }
  2. 算法二:穷举,但是只使用了两层循环

    public static int maxSubSum(int [] a) {
    int maxSum = 0;
    for(int i = 0;i<a.length;i++) {
    int thisSum = 0;
    for(int j = i;j < a.length;j++) {
    thisSum += a[j];
    //每加一次判断一次,这样就可以使j既可以当结束位置,也可以当每个数的下标
    //省去了一层for循环
    if(thisSum > maxSum) {
    maxSum = thisSum;
    }
    }
    }
    return maxSum;
    }

  3. 算法三,分治(divide-and-conquer)策略

递归调用的一般形式是传递输入的数组以及左边界和右边界,它们界定了数组要被处理的部分。单行驱动程序通过传递数组以及边界0和N-1将程序启动

   分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

   分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

   如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

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

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

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

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

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

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

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

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

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

	分治法在每一层递归上都有三个步骤:

	    step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

	    step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题

	    step3 合并:将各个子问题的解合并为原问题的解。

		可使用分治法求解的一些经典问题

		 (1)二分搜索
		(2)大整数乘法
		 (3)Strassen矩阵乘法
		(4)棋盘覆盖
		(5)合并排序
		(6)快速排序
		(7)线性时间选择

		(8)最接近点对问题
		(9)循环赛日程表
		(10)汉诺塔
		**依据分治法设计程序时的思维过程

		    实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。
		1、一定是先找到最小问题规模时的求解方法
		2、然后考虑随着问题规模增大时的求解方法
		3、找到求解的递归函数式后(各种规模或因子),设计递归程序即可。
  1. 算法4: 联机算法(只对数据进行一次扫描,不需要再次记忆,在任意时刻,算法都能对他已读入的数据给出子序列问题的正确答案)

    public static int maxSubSum(int [] a) {
    int maxSum = 0,thisSum = 0;
    for(int j = 0;j<a.length;j++) {
    thisSum += a[j];
    if(thisSum > maxSum) {
    maxSum = thisSum;
    }else if(thisSum < 0) {
    thisSum = 0;
    }
    }
    return maxSum;
    }

运行时间中的对数

  1. 折半查找

    给定一个整数X和整数A0,A1,...,An-1,后者已经预先排序并在内存中,求下标i使得Ai=X,如果X不在数据中,则返回i

程序如下:

public static  int binarySearch(
	int [] a,int x
	){
int low = 0,high = a.length - 1;
while(low <= high) {
	int mid = (low + high) / 2;
	if(a[mid] < x) {
		low = mid + 1;
	}else if(a[mid] > x) {
		high = mid - 1;
	}else {
		return mid;
	}
	}

	return -1;
}
  1. 欧几里得算法

    求两个正整数的最大公因数

程序如下:

public static long gcd(long m,long n) {
while(n != 0) {
	long rem = m % n;
	m = n;
	n = rem;
}
return m;

}
  1. 幂运算

    处理一个整数的幂

程序如下:


标题:2.算法分析
作者:mahaonan
地址:https://mahaonan.fun/articles/2022/07/18/1658147078282.html