算法与时空复杂度

印度阿三17 2020-03-13

展开全文

一、补充：递归相关知识

1.1 递归定义

· 程序调用自身的编程技巧称为递归（ recursion）。

1.2 斐波那锲数列

0 1 1 2 3 5 8 13 21 34 .......

fi𝑏(𝑛) ::= 𝑓𝑖𝑏(𝑛 − 1) 𝑓𝑖𝑏(𝑛 − 2), 𝑛 > 1
| 1 ,𝑛 = 1
| 0 ,𝑛 = 0

int Fib(n)
{
    if(n<=1)
    return n;
    else
    return Fib(n-1) Fib(n-2);
}

二、算法的基本概念

2.1 定义

· 对特定问题求解步骤的一种描述，是指令的有限序列

2.2 算法的五个基本特征

有穷性：算法运行的步数是有限的，运行的时间也是有限的

确定性：对同一输入每次都有相同的输出

可行性：算法中描述的操作都是可以通过已实现的基本运算执行有限次实现

输入：有0个或多个输入

输出：有1个或多个输出

三、好的算法应考虑的目标

正确性：算法能正确的解决问题

可读性：算法应具有良好的可读性，以便于人们理解

健壮性：也称鲁棒性，当输入非法数据时算法也能适当做出反应或进行处理

效率：算法执行的时间尽可能短

低存储：算法执行过程中所需要的最大存储空间应尽可能小

四、算法的效率度量：时间复杂度和空间复杂度

4.1 时间复杂度

· 一个语句的频度指语句在算法中被重复执行的次数

· 算法中所有语句的频度之和记作T(n)

· 时间复杂度主要分析T(n)的数量级

· 通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度

· T(n) = O(f(n)

4.2 空间复杂度

· 算法所耗费的存储空间g(n)

· 它是问题规模n的函数，记为S(n)

· S(n) = O(g(n))

4.3 注意

注意：算法原地工作指算法所需辅助空间是常量，即S(n) = O(1)

4.4 非递归程序的时间复杂度分析

计算语句频度之和f(n)

4.5 递归程序的时间复杂度分析

分治法主定理：T(n) = aT(n/b) f(n)，n为问题规模，a>=1和b>1是常量，f(n)是递归以外的计算时间

若f(n) = O(𝑛^logb^(𝑎−𝜀))对于某个𝜀 >0成立，那么T(n) = O(𝑛^log𝑏^𝑎)

若f(n) = O(𝑛log𝑏^𝑎)，那么T(n) = O(𝑛^log𝑏^𝑎 * logn)

若f(n) = O(𝑛log𝑏^(𝑎 𝜀))对于某个𝜀 >0成立，并且af(n/b)≤cf(n),对于某个常量c<1(n足够大)成立，那么T(n) = O(f(n))

//no1
理解：比较f(n)与𝑛^log𝑏^𝑎的大小
谁大T(n)就取它,相等时T(n) = O(𝑛^log𝑏^𝑎 * logn)
T(n)   = aT(n/b) f(n)
T(n/b) = aT(n/𝑏^2) f(n/b)
T(n)   = a[ aT(n/𝑏^2) f(n/b) ] f(n)
       =𝑎2T(n/𝑏^2) af(n/b) f(n)

//no2
例子：迭代表达式T(n) = 3T(n/2) n^2
解析：1.验证是否满足主定理
      2.验证满足哪种情况
      3.根据主定理求解
该迭代式满足主方法
比较f(n)与𝑛^log𝑏^𝑎的大小有n^log2^3 < 𝑛^2
满足情况第三种且3(𝑛^2)/4 < 𝑐𝑛^2
故T(n) = O(𝑛^2)

【例子】（2012华中科技大学887）汉诺塔问题
 假定move()的时间复杂度为O(1),则下列算法的时间复杂度是 （ ）
void hanoi(int n,char x,char y,char z)
{ 
    if(n==1)
        move(x,1,z);
    else
    {
        hanoi(n-1,x,z,y);
        move(x,n,z);
        hanoi(n-1,x,z,y);
     }        
}