4.算法分析

4.1 算法分析概述

算法分析目的：分析算法的时空效率以便改进算法性能。

4.2 算法时间复杂度分析

• 一个算法是由控制结构（顺序、分支和循环三种）和原操作构成的。

1. 顺序结构：按照所述顺序处理
   分支结构：根据判断条件改变执行流程
   循环结构：当条件成立时，反复执行给定的处理操作
2. 指固有数据类型的操作，如+、-、*、/、++和–等

• 算法执行时间取决于两者的综合效果。

4.2.1 算法分析方式

• 事后分析统计方法：编写算法对应程序，统计其执行时间。
  编写程序的语言不同，执行程序的环境不同以及其它因素造成不能用绝对执行时间进行比较。
  
• 🚩 事前估算分析方法：撇开上述因素，认为算法的执行时间是问题规模n的函数。
  

4.2.2 分析算法的执行时间

• 求出算法所有原操作的执行次数（也称为频度），它是问题规模n的函数，用T(n)表示。
• 算法执行时间大致 = 原操作所需的时间×T(n)。所以T(n)与算法的执行时间成正比。为此用T(n)表示算法的执行时间。
• 比较不同算法的T(n)大小得出算法执行时间的好坏。

4.2.3 算法的执行时间用时间复杂度来表示

算法中执行时间T(n)是问题规模n的某个函数f(n)，记作：T(n) = O(f(n))

记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同 --> 趋势分析

也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。

本质上讲，是一种T(n)最高数量级的比较。

例如：T(n) = 2n 2 n^2n2+2n+1 = O(n 2 n^2n2)

📝 一般地：

• 一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。
• 一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。
• 其余常用的算法时间复杂度还有平方阶O(n 2 n^2n2)、立方阶O(n 3 n^3n3)、对数阶O(l o g 2 n log_2nlog2n)、指数阶O(2 n 2^n2n)等。

各种不同算法时间复杂度的比较关系如下：

算法时间性能比较：假如求同一问题有两个算法：A和B，如果算法A的平均时间复杂度为O(n)，而算法B的平均时间复杂度为O(n 2 n^2n2)。　　一般情况下，认为算法A的时间性能好比算法B。

某算法的时间复杂度为O(n 2 n^2n2)，表明该算法的执行时间与n 2 n^2n2成正比。

4.2.4 简化的算法时间复杂度分析

算法中的基本操作一般是最深层循环内的原操作

在算法分析时，计算T(n)时仅仅考虑基本操作的运算次数

算法执行时间大致 = 基本操作所需的时间×其运算次数

4.2.5 最好、最坏和平均时间复杂度分析

4.2.6 算法空间复杂度分析

空间复杂度：用于量度一个算法运行过程中临时占用的存储空间大小(算法中需要的辅助变量所占用存储空间的大小)。一般也作为问题规模n的函数，采用数量级形式描述，记作：S(n) = O(g(n))

若一个算法的空间复杂度为O(1)，则称此算法为原地工作或就地工作算法。该算法执行所需辅助空间大小与问题规模n无关。

❓ 为什么空间复杂度分析只考虑临时占用的存储空间

⭐️ 分析如下算法的空间复杂度

// 临时占用的存储空间：函数体内分配的空间
int fun(int n){  
 int i，j，k，s;
 s=0;
 for (i=0;i<=n;i++)
     for(j=0;j<=i;j++)
         for (k=0;k<=j;k++)
             s++; 
 return(s)
}

📝 算法中临时分配的变量个数与问题规模n无关，所以空间复杂度均为O(1)

5.数据结构+算法=程序

5.1 程序和数据结构

• 程序总是以某些数据为处理对象。将松散、无组织的数据按某种要求组成一种数据结构，对于设计一个简明、高效、可靠的程序是大有益处的。
• 沃思：程序就是在数据的某些特定的表示方法和结构的基础上，对抽象算法的具体表述，所以说程序离不开数据结构。
• 程序是通过某种程序设计语言描述的，程序设计语言具有实现数据结构和算法的机制，其中类型声明与对象定义用于实现数据结构，而语句实现实现算法，描述程序的行为。

5.2 算法和程序

• 由程序设计语言描述的算法就是计算机程序。
• 对一个求解问题而言，算法就是解题的方法，没有算法，程序就成了无本之末，无源之水，有了算法，将它表示成程序是不困难的。
• 算法是程序的灵魂。算法在整个计算机科学中的地位都是极其重要的。

5.3 算法和数据结构

✏️ 数据结构角度求解问题的过程

数据结构观

编程一般过程

软件工程思想

• 问题求解 --> 算法设计
• 算法实现 --> 选择合适的存储结构
• 存储结构设计取决于数据的逻辑结构，并且为运算高效实现服务。

• 程序员可以直接使用它来存放数据 —— 作为存放数据的容器。
• 程序员可以直接使用它的基本运算 —— 完成更复杂的功能。

5.4 数据结构的发展

6.总结

6.1 从数据结构角度求解问题的过程

✏️ 设计集合的顺序存储结构类型如下：

typedef struct    //集合结构体类型
{  
    int data[MaxSize];  //存放集合中的元素，其中MaxSize为常量【静态分配方式】
    int length;         //存放集合中实际元素个数
}  Set;              //将集合结构体类型用一个新类型名Set表示

✏️ 采用Set类型的变量存储一个集合

• createset(Set &s，int a[]，int n)：创建一个集合
• dispset(Set s)：输出一个集合
• inset(Set s，int e)：判断e是否在集合s中
• add(Set s1，Set s2，Set &s3)：求集合的并集
• sub(Set s1，Set s2，Set &s3)：求集合的差集
• intersection(Set s1，Set s2，Set &s3)：求集合的交集

//创建一个集合
void createset(Set &s，int a[]，int n)
{  
    int i;
    for (i=0;i<n;i++)
        s.data[i]=a[i];
    s.length=n;
}
//输出一个集合
void dispset(Set s)
{  
    int i;
    for (i=0;i<s.length;i++)
        printf("%d "，s.data[i]);
    printf("\n");
}
//判断e是否在集合s中
bool inset(Set s，int e)  
{  
    int i;
    for (i=0;i<s.length;i++)
        if (s.data[i]==e)
            return true;
    return false;
}
//求集合的并集
void add(Set s1，Set s2，Set &s3) 
{  
    int i;
    for (i=0;i<s1.length;i++) //将集合s1的所有元素复制到s3中
        s3.data[i]=s1.data[i];
    s3.length=s1.length;
    for (i=0;i<s2.length;i++) //将s2中不在s1中出现的元素复制到s3中
        if (!inset(s1，s2.data[i]))
        {  
            s3.data[s3.length]=s2.data[i];
            s3.length++;
        }
}
//求集合的差集
void sub(Set s1，Set s2，Set &s3) 
{  
    int i;
    s3.length=0;
    for (i=0;i<s1.length;i++) //将s1中不出现在s2中的元素复制到s3中
        if (!inset(s2，s1.data[i]))
        {  
            s3.data[s3.length]=s1.data[i];
            s3.length++;
        }
}
//求集合的交集
void intersection(Set s1，Set s2，Set &s3)  
{ 
    int i;
    s3.length=0;
    for (i=0;i<s1.length;i++) //将s1中出现在s2中的元素复制到s3中
        if (inset(s2，s1.data[i]))
        {  
            s3.data[s3.length]=s1.data[i];
            s3.length++;
        }
}

6.2 算法描述―输出型参数

返回值 函数名(输入参数， 输出参数)  //输出参数 --> 采用引用类型参数
{
     //实现代码;
}

确定问题规模n

找基本操作语句

求基本操作的执行次数T(n)

用复杂度表示T(n)