欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法导论一-算法分析

程序员文章站 2022-03-11 23:29:42
...

一,插入排序: 插入的定义排序简单来说,就是把待排序值通过比较交换的方式插入到已排序的列表中。

  • 找了个比较形象的图:
    算法导论一-算法分析
  • 一个简单的例子:
#如待排列表为: [3,4,1,2,4,5]
#由于第一个是排好序的,因此我们从第二个开始比较。
#第一次排序结果:  [3,4,1,2,4,5]
#第二次排序结果:  [1,3,4,2,4,5] 。
#得到第二次结果的数据移动情况: [3,4,1,2,4,5]  => [3,1,4,2,4,5] =>[1,3,4,2,4,5] =>结束第二次
#第三次排序结果: [1,2,3,4,4,5] 
#得到第三次结果的数据移动情况:[1,3,4,2,4,5]  = [1,3,2,4,4,5] => [1,2,3,4,4,5]  => [1,2,3,4,4,5]
#第四次排序结果: [1,2,3,4,4,5] 
#得到第四次结果的数据移动情况: [1,2,3,4,4,5]  =>  [1,2,3,4,4,5] 
#第五次排序结果: [1,2,3,4,4,5]
#得到第四次结果的数据移动情况: [1,2,3,4,4,5]  =>  [1,2,3,4,4,5] 
  • 根据定义,可以简单写出代码:
public void insertSort(int arr[]){
	for(int i=1;i<arr.length;i++){ //外层控制开始排第几个。
		for(int j=i; j>0 && arr[j]< arr[j-1];j--){  //内层控制比较和交换。
			int tmp = arr[j-1];
			arr[j-1] = arr[j];
			arr[j] = arr[j-1]; 
		}
	}
}

二,算法的运行时间. 考虑上面插入算法的例子:

  • 给定的数据。如,对于上面的例子,排好序的序列会相对快,最差的则是逆序;
  • 数据的规模。如,排10个和100000000个时间明显不同。我们在算法中,一般将输入的规模参数化,将运行时间看做规模的函数。
  • 运行时间的上界。在最坏的给定数据下,运行时间与数据规模的函数关系,以此我们才能做出保证,这也是算法最关注的分析。

三,算法分析 T(n)

  • 最长时长,T(n) = max time on any input of size n.
  • 平均时长(期望时长) T(n)= 输入规模n下所有可能输入的期望时间,即所有可能出现的n*出现的概率相加取平均值(加权平均),一般我们假设所有输入等可能出现。
  • 最好情况(假象):只对特定输入有效,一般不考虑。

四,渐进分析:关注运行时间的增长速度,忽略依赖于机器的常量,弃去低阶项,只关注最高阶。因为当n足够大时,最终是由最高阶影响其增长速度。渐进符号θ。

  • 如: 3n³+2n²+5n+100 = θ(n³)

五,继续分析插入排序

  • 最坏情况:即逆序情况,把交换移动看做常数项,只关注循环次数。可以发现,i=2时,j一次; i=3时, j 两次。可以得到如下(即等差数列的和):
    T(n) = 1+2+3+…(n-1) = θ(n²)
  • 对于小n,速度比较快,但是增长很快。

六,归并排序 将已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

  • 归并,简单来说,两个排序序列,每次取其最小的值,写到第三个序列中,最好得到的序列也是排好序,并且是原先两个序列的合并。
  • 可以发现,归并操作是一个线性时间。完全遍历两个序列即可。
  • 时间: T(n) = 分解的子序列和+合并子序列时间<线性>。 即 T(n) = 2T(n/2) + θ(n)
  • 找了一个比较形象的图:算法导论一-算法分析
  • 可以看到,首先是向下分解,是常数时间。然后向上归并,可以发现,每层都要遍历n个数,即每一层都需要线性时间。那么总时间为: 层数*n .
  • 那么到底有多少层。log n 层。我们可以看到,序列数每次其实都在2分,即, 2 的x 次方要大于等于n。要求x,这里是取以2为底,n的对数。即 log n.
  • 因此归并排序 T(n) = θ(n log n) , 这个在n比较大时远小于 n²