算法复杂度

一般执行一个算法花费的时间短,需要空间少,则认为这个算法是好的。但是,确定一个算法的好坏程度,最重要的因素还是在于执行时所需要的时间。

度量时间复杂度可以通过编程实现,但是所受的外来影响太多,比如语言性能、操作系统、机器性能、编程能力等。
所以在算法分析中,选择出现在算法中某个特定的执行步,通过数学分析来确定完成该算法所需要的步数。
在排序算法中,一般认为数据项的比较是不可回避的,所以用比较项来度量各种排序算法的时间复杂度。
在另外的情况中,可能数据移动是更花费时间的,那么就需要用数据移动来衡量算法的时间复杂度。
1、问题复杂度
问题包含难问题(difficult problem)与易问题(easy problem)
如果一个问题可以被有效算法解决,多半算法具有多项式时间(polynomial -time)复杂度,那么该问题称为易问题。
相反,如果一个问题不能够被任何具有多项式时间的算法解决,那么它一定是难问题。

2、时间复杂度的定义
如果一个算法花费了(N^3 + N)步数,通常认为改算法的时间复杂度是O(N^3)。
本科的时候数据结构也是这么简单的提到过,下面才是正式且精确的数学定义:

定义:当且仅当存在两个正常数 c 和 n0 ,对于所有的 n >= n0,使得|f(n)| <=  c|g(n)|,那么定义 f(n)=O(g(n))。

随着n的逐渐变大,f(n)是以g(n)为界限的。如果有这么一个算法,他的时间复杂度是O(g(n)),存在常数C,当n足够大的时候,该算法 的时间复杂度总小于C倍的 g(n)

3、时间复杂度函数,数量级如下图:

时间复杂度
4、一个具有时间复杂度为O(p(n))的算法,其中p(n)是一个多项式函数,称为多项式算法(polynomial algorithm)。
不是以多项式函数为界的时间复杂度算法称为指数算法(exponential algorithm)

5、复杂度 符号表达的意思

复杂度表示的意思

6、时间复杂度一般性关系

时间复杂度一般性关系

 

o(N^3) 的时间复杂度不一定就比o(N)高!
条件成立:当且仅当N足够大的时候才成立N

7、直接插入排序算法,是将数字序列 x1,x2,x3,x4… 分为无序区与有序区两部分,逐步将无序区的数字插入到有序区。
1)如果选取无序区第一个数字,从有序区最后向前一个一个比较数字大小,叫做直接插入排序算法
2)如果选取无序区第一个数字,在有序区折半查找位置,叫做折半插入排序算法
3)如果选取无序区最小的数字,插入到有序区最后一个位置,叫做选择插入排序算法

 

 

直接插入算法例子:数字序列 3、5、1、6、7、2、9
初始状态:有序区:{}         无序区 {3、5、1、6、7、2、9} tmp=3
第一步:有序区:{3}         无序区 {5、1、6、7、2、9} tmp=5
拿5和3比较,5更大,3不需要向后移动,将5放到3后面
第二步:有序区:{3、5}         无序区 {1、6、7、2、9} tmp=1
拿1和5比较,1更小,5后移动1位
第三步:有序区:{3、、5}        无序区 {6、7、2、9} tmp =1,5把1的位置占用了,其实有序区现在是3、5、5
再拿1和3比较,1更小,3后移动1位,再将1插入3原来在的位置
第四步:有序区:{1、3、5}         无序区 {6、7、2、9} tmp =6
第五步:有序区:{1、3、5、6}         无序区 {7、2、9} tmp=7
第六步:有序区:{1、3、5、6、7}         无序区 {2、9} tmp=2
第七步:有序区:{1、2、3、5、6、7}         无序区 {9} tmp=9
第八步:有序区:{1、2、3、5、6、7、9}         无序区 {}

 

直接插入排序算法的伪代码:
输入序列:x1,x2,x3,x4,x5….
输出有序的序列

For j := 2 to n do
  Begin
  i:=j-1;
  tmp = x[ j ]
	While tmp < x[ i ]  And  i > 0 do
	Begin
	x[ i+1 ] := x[ i ]
	i := i -1
	End
  x[ i+1 ] := tmp
  End

在算法分析中,将赋值语句的次数当做算法时间复杂度的度量。
可以看到有两重循环,外层由 2 到 n,每次有两个赋值操作 tmp = x[ j ] 和 x[ i+1 ] := tmp,
内层次数根据tmp大小 而变化,记为dj,表示第 j 个数需要插入有序区所需要的步数
总移动次数

移动次数

最好的情况就是数列已经按序排好了,不需要内层的赋值操作了, X = 2(n-1) = O(n)
最坏的情况就是数列是逆序的
d2 赋值1次
d3 赋值2次
d4 3次
d5 4次

dn n-1次
那么 X = 2(n-1)+{ [1+(n-1)] * (n-1)}/2
即 X = 2(n-1)+n(n-1)/2 = O(n^2)

平均情况
如果将x插入到有序数列 x1,x2,x3,…, xk 中,
可能的情况有,
1、有序数列不动,需要移动0次,即1/k的概率出现这种情况,需要移动 0次*1/n
2、有序数列只需要移动最大的数字,移动 1 次,1*1/n
3、有序数列只需要移动第二大的数字,移动 2 次,2*1/n
。。。
所以x插入有序数列的赋值移动次数平均为:

 

赋值移动次数平均

加起来就是:

平均

X = 2(n-1)+n(n-1)/4 = o(n^2)

 

8、折半查找算法分析
已知有序数列a1,a2,a3,a4…,an ,折半查找就是在有序数列中,每次从中间开始查找目标值 X
伪代码如下:
输入有序数列 a1,a2,a3,a4,….,an,目标值 X,其中a1<=a2<=a3<=a4….<=an
输出:如果aj = X,那么输出 j ,如果不存在这样的 j 使得 aj = X 那么输出 0

left := 1;
right := n;
While left <= right
	Begin
	j := (left + right) / 2;  //向下取整,比如(1+4)/2 =2
	if a[ j ] = X  output j and stop;
	if a[ j ] < X   left := j - 1;
	else right := j + 1; 
	End 
j := 0;//当没有找到 x 的时候,在这步赋值 j 为0,然后输出
output j

 

折半查找可能查找到X,可能超找不到X,所以计算复杂度的时候需要考虑这两种情况。

折半查找可以做事一个二叉查找树,如下图所示一个完全二叉树,1、2、3、… 、14、15,(记为 2^i – 1 个数字)
可以看到最快一步找到8,
最长步数就是(树高+1)3+1=4步,找到 X 最长是4步,没找到 X 最长也是4步。
例子中树高是3 ,根节点算0层(也有的书会看做为1层,这里的描述算是 0层)
最长步数 :共 logN+1 步,
最好:根节点,1步结束=θ(1)[成功]
最差:树高+1 次结束=logN +1 = θ(log N)
下面算平均情况

平均情况

 

有N个数,查找 X 成功的情况有 N 个,查找不到 X 的情况有N +1 个,
N+1是怎么来的呢?N个数,有N+1个缝隙,比如这个 : []1[]2[]3[]4[]5[]
根节点1个,成功搜索到1次
第一层2个节点,成功搜索到2次
第二层4个节点,成功搜索到4次
第三层8个节点,成功搜躲到8次
所以成功搜索到的次数,K表示深度,即 logN+1

2i-1

 

搜索不成功的情况只有 N+1 次,每一次都要搜索到叶子节点去,所以是 K*(N+1)步数
1/(2N+1)表示的是概率
计算A(n)这个多项式(通过 2*A(n)与A(n)求差,可以计算出来),得到结果约等于 K 即 logN
综上,折半查找的时间复杂度如下:

最好情况:只需1步 Θ(1)

平均情况:Θ(logN)

最差情况:Θ(logN)

 

 

9、直接选择排序
向前面所介绍的,选取无序区最小的数字,和ai交换(ai是无序区的第一个数字)
伪代码如下:
输入:a1,a2,a3,a4…,an(无序)
输出:a数列的有序数列

For i := 1 to n-1  do
Begin
min := i
k := i+1
For k:= i+1 to n   do
	if (ak < a min) min = k;
swap( a min ,  ai )
End

对每一个数字,
比较的复杂度:Θ(n),移动复杂度:Θ(1)

最好的情况下,直接选择排序整体的算法复杂度:
比较的复杂度:n(n-1)/2 即 Θ(n^2)
移动的复杂度:Θ(n)

最坏情况下,同样是:
比较的复杂度:n(n-1)/2 即 Θ(n^2)
移动的复杂度:Θ(n)

同样,也可以使用min改变的次数度量算法复杂度。
两个元素进行比较的次数是一个固定数 n(n-1)/2 即 Θ(n^2)

最好情况:O(1)
平均情况:O(nlogn)
最坏情况:O(n^2)

10、快速排序算法,理解就是挖坑法
伪代码:

Input:af,af+1,...,aL
Output:排好序的 af,af+1,...,aL 数列
If f>= L then Return
X:=af
i:=f
j:=L
while i < j do
Begin
	while aj >= X do
		j:= j-1;
	ai <-> aj
	while ai <= X do
		i:= i+1;
	ai<->aj;
End
QuickSort( f,  j-1 )
QuickSort( j+1, L ) 

快排主要思想

快排是一种分而治之的策略,当X正好在中间位置将序列划分成两个子序列,此时快排呈现出最好的情况,就相当于X左边的元素数和X右边的元素数是相等的,相当于等分了。第一次需要 N 步将数列分成两个子数列,第二次需要 2*( N/2)=N 步 ,第三次需要4*(N/4)=N 步 ,假设N = 2^k ,总共需要 K 次,K = logN,每次需要N步,最好情况下时间复杂度O( NlogN )
最好情况类似于:
bestcase

最差情况就是这棵树只有右子树,或者左子树,每次选的 X 都是最大或最小
最坏情况下的时间复杂度:n+(n-1)+…+1 =(n+1)n/2= Θ(n^2)

平均情况下,假设第一次分成的树左右比例为 A:B,每次左右比例都是A:B,能想到树的深度是logN,每次都是A+B=N次,复杂度还是NlogN
数学推导可以看下面,
T(n)表示在平均情况下对n个元素执行快速排序所需要的步数,分了两部分,s 和 n-s
S的取值范围由1到n,这n个数可能分为(1,n-1),也可能分成(2,n-2)等,平均C层,每层算n次

n
又知道:
youzhidao
可以推出:
tuichu

最好情况:O(nlogn)
平均情况:O(nlogn)
最差情况:O(n^2)

 

Tagged on:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.