【算法设计与分析】期中复习

咸鱼的小世界 / 2023-05-04 / 原文

一、概论

算法是求解问题的一系列步骤，用来将输入数据转换成输出结果

有限性：算法的的执行步骤是有限的，每个步骤都在有限时间内完成，即算法可在有限时间内被只执行完成
确定性：算法中每一条指令都有确切的含义，没有二义性（例：取出数组中差不多大的数，取出数组中最大的数）
可行性：算法的每个步骤都是可实现的，例如：整数乘法操作可用加法运算实现，乘2操作可用移位运算实现（表达算法中的操作可以被实现，对计算机而言，要有对应的指令，对人而言，要有步骤，纸，笔）
输入性：0个或多个
输出性：1个或多个

答：第一段代码是一个死循环，违反了算法的有限性。第二段出现了零除错误，违法了算法的可行性。

以设计求1＋2＋…＋n的值的算法为例说明C/C++语言描述算法的一般形式

在设计算法时，如果某个形参需要将执行结果回传给实参，需要将该形参设计为引用型参数。

算法+数据结构=程序（Niklaus Emil Wirth, 1934-）
联系：数据结构是算法设计的基础。算法的操作对象是数据结构，在设计算法时，通常要构建适合这种算法的数据结构。数据结构设计主要是选择数据的存储方式，如确定求解问题中的数据采用数组存储还是采用链表存储等。算法设计就是在选定的存储结构上设计一个满足要求的好算法。
区别：数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。

算法分析是分析算法占用计算机资源的情况。
算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。

符号：
1. 上界：O(n)（主要用这个）
2. 下界：Ω(n)
3. 同阶：
计算
1. 大吞小，常系数删掉
2. O(3n+2)=O(3n)=O(n)
3. O(6n²+3n+2)=O(6n²+3n)=O(6n²)=O(n²)
4. O(1)：常数时间复杂度，即算法执行时间不会随着问题规模的增大而增大
5. 【例1.3】分析以下算法的时间复杂度
```
void fun(int n)
{
    int s=0,i,j,k;
    for (i=0;i<=n;i++)
        for (j=0;j<=i;j++)
            for (k=0;k<j;k++)
                s++;
}
```
  补充：对该问题而言，有几层for循环就是n的几次方，如果再加一层for循环for(l=0;l<k;i++），则时间复杂度为O(n⁴)
算法的三种情况
1. 最好：算法基本语句执行的最小次数
2. 最坏：算法基本语句执行的最大次数
3. 平均：各种特定输入下的基本语句执行次数的带权平均值