算法设计分析内容总结【考试后会对试题进行分析】

---

主要内容：扎实算法设计理论知识，应对算法理论考试，对之前所学做汇总:deciduous_tree:

简单描述一下各个算法的思想，简单举例【时间不够，所以就不详细扩展了】

---

算法的定义和性质

首先扯点用处不大的东西，算法的由来是波斯著名的学者花拉子密的《印度数字算术》，花拉子密的音译即为“算法” — algorithm ；1936年图灵提出了图灵机，通过计算机模型，刻画计算机的计算行为，1946年，现代计算机之父-冯 诺伊曼提出了存储程序原理

• 计算问题 ： 给定数据输入，计算满足某种性质输出的问题 – 平时做了很多，每个算法问题都是一个计算问题

• 给定计算问题，算法就是一系列良定义的解决问题的步骤【指令】

  • 有穷性 ：算法的执行步骤必须是有限的，不会一直执行 ----- 这里可以举几个例子 ：给定输入的数组，不断交换首尾元素的位置 — 【这不是算法】 没有终止，也没有输出；
  • 确定性： 算法必须是没有歧义的 — 给计算机的指令明确； 给定输入的数组，交换两个数的位置 --【这不是算法】 没有明确是哪两个数，不能设计步骤来解决问题 ； 对于选择排序，算法就是每次找到最小的元素，排在前面；之后又在剩下的元素中找最小元素；这步骤指令是明确的
  • 可行性： 可以机械地一步一步执行基本操作步骤。 也就是可以将问题拆解为一步一步的求解步骤 —将大元素放在数组后面，小元素放在数组前面 ---- 其实这里既不满足可行性，也不满足确定性
  • 输入
  • 输出

简单理解，算法就是对于一个确定的计算问题，所给出的准确定义的一系列解决问题的步骤。这些步骤转化为指令，交由计算机执行解决问题。 算法必须是有限步骤，并且是指令明确的，并且还要可行，可以很容易将步骤转化为计算机的指令。也即是有穷性，可行性，确定性

算法的表示

算法的描述有多种方式：自然语言 ----- 人类使用自然语言交流与表达算法 ；不便之处：语言描述繁琐，容易产生歧义，使用了“……”不严谨的描述 编程语言 ： 机器作为算法的执行者，需要详细具体的代码 – 不便的地方就是不同的编程语言存在差异

伪代码 ：非正式语言 — 移植编程语言书写形式作为基础和框架，接近自然语言的形式表达算法的过程。

比如选择排序🌲

自然语言描述 — 第一次遍历找到最小元素放在数组最前面，第二次找到次小元素，……第n次找到剩余数组中第n小的元素

编程语言描述

void  collectSort(int* arr,int num)
{for (int i = 0; i < num - 1; i++){int pos = i;int min = arr[i];for (int j = i; j < num; j++){if (arr[j] < min){min = arr[j];pos = j;}}int temp = arr[pos];arr[pos] = arr[i];arr[i] = temp;}
}

所以也可以用伪代码描述，比如交换三行代码，直接写成交换节点就可以了。

伪代码的书写约定

• 最前面定义算法的输入和输出
• 循环语句块缩进 – 和编程语言一样
• 赋值采用箭头 i + 1 → j
• 注释和编程语言一样
• 条件语句块缩进
• 不关注细节

算法的分析

比如对于同一个计算问题，有多种算法解决，比如排序问题，冒泡，选择，插入—希尔，怎么比较性能？

这里我们就需要分析算法的时间 — 但是分析运行时间需要独立于机器，也就是不要让外部的变量影响比较，对于相同的输入规模，实例是也会影响运行的，比如对于插入排序，插入排序就是和之前拍好序的最大元素比较，所以最好的情况就是数组升序，此时比较的次数就是n-1次。而最坏的情况即使数组降序，这时就要比较n(n-1)/2

那么我们分析算法，是分析最好情况，还是最坏情况呢，最好情况不好出现，不具有普遍性，最坏情况，可以确定上界，更具有一般性------ 因此我们经常使用最坏情况来分析算法的运行时间

这里就引入了语句的频度来计算每行代码的执行次数，从而来统计算法的规模，当数据充分大时，会发现最高次项次数相同的代码的运行时间趋向于相同， 因此就忽略Tn的系数和低阶项，只关注高阶项，用O(n)表示

O的定义【函数的渐近紧确界】

上面对于O有了一个模糊的概念，O时用来表示算法规模的最高阶的规模的。

对于给定的函数g(n),O(g(n))表示下列函数的集合

O(g(n)) = {T(n) :存在c1,c2,n0 > 0, 使得对于任意 n >= n0, c1g(n) <= Tn <= c2g(n)}

比如对于COSn，cosn <= 1; 那么 cosn = O(1)

log7 n = log2 n / log2 7 = O(log2 n) = O(logn)

算法运行时间成为算法的时间复杂度，通常使用渐近号O表示

算法分析 — 同一机器的性能 ，分析最坏情况 ， 采用渐近分析

这就是算法的几个重要的模块，之前博主已经从八皇后为引，从深度优先搜索开始分析，到后面分析记忆化搜索，也就是动态规划，之后以循环赛问题分析了分治算法，最后又分析了广度优先搜索。但是没有很系统，这里放一张图，大概明确算法所包括的几个重要的组成部分。

各算法思想

分治算法

基本思想 ： 将原问题分解为K个规模较小的子问题，这些子问题相互之间独立而且和原问题相同，递归解决这些子问题，将所有子问题的解合并得到原问题的解

也就是 分解原问题 ---- 解决子问题 ---- 合并子问题 ；关键就是独立

比如归并排序

void mergeSort(int *arr, int low, int high)
{if(high > low)//开闭只要保持统一就可以了{mid = low + (high - low)/2;mergeSort(arr,low,mid);mergeSort(arr,mid +1;high);merge(arr,low,mid,high);}
}

那么归并排序的时间复杂度怎么计算呢？

这里问题的规模被缩小变成T n/2; 因为这里的递归形成了一个深搜的树结构，那么，问题规模由于二分法不断缩小，最后只剩下O(1), 第一层的规模为n，代价为O(n),第二层规模为n/2，但是有2个子节点，所以代价还是O(n);……每层的代价都是O(n),那么整个树结构的代价就是n * 层数

搜索树一有log2 n层，所以整个算法的时间复杂度也即是O(nlogn)

比如循坏赛

void EightRoundrobin(int start,int end)
{if(end > start) //当end和start相等的时候就结束递归了{int mid = start + (end - start)/2;EightRoundrobin(start,mid -1);EightRoundrobin(mid + 1,high);merge(start,mid,high);}
}

分析的时候就按照子问题已经解决，所以分治算法就是将原问题分解为独立的子问题，然后将子问题合并，递归解决子问题。

这里可能会考察几种排序算法的时间复杂度，在此处附上

比较容易考察的是快速排序和归并排序， 平均算法复杂度都是O(nlogn)，因为都是树结构，使用的都是分治思想，但是归并排序最坏算法复杂度也是O(nlogn),快速排序的最坏算法复杂度是O(n^2), 并且其空间复杂度为O(nlogn)，因为每次都需要一个辅助空间

最简单的基础的三种排序【冒泡，选择，直接插入】的算法复杂度都是O(n^2);

动态规划

基本思想 ：将原问题先分解为若干个子问题，按顺序求解子问题，前一阶段的子问题为后一子问题的求解提供了信息，求解任意子问题时，列出所有可能的局部最优解，通过决策保留最可能的最优解，最后一个问题子问题的解就是原问题的解【dp – 递推，所以有依赖关系】
基本步骤

• 将原问题划分为若干子问题
• 确定状态和状态变量
• 确定决策并写出状态转移方程
• 寻找边界条件
• 以自底向上的方式得到最优值

基本要素

• 最优子结构 ： 原问题的最优解包含了其子问题的最优解 动态规划中，利用问题的最优子结构性质，自底向上的方式从子问题最优解构造出原问题的最优解
• 子问题重叠 使用记忆化搜索自顶向下时，每次产生的子问题不总是新问题，也就是子问题不都是独立的，一个子问题在下一阶段的决策可能多次用到

回溯算法【深度优先搜索】

基本思想 ： 按照深度优先的策略，从根节点触发搜索解空间树，当搜索到某一节点，判断该节点是否包含问题的解，若包含，就从节点出发继续搜索下去，若不包含，就逐渐向祖先节点回溯

一般模式 ： 子集树 ，排列树

• 当求解的结果为集合S的子集的时候，问题的解空间树为子集树 【加入或不加入】0-1背包
• 当求解的结果为集合S的排列的时候，问题的解空间树为排列树 【排列】八皇后

//子集树
void dfs(int t) //当前的位置，层数
{if(t > n)output(f);elsefor(int i = 0; i <= 1;i++)//只有两种可能，加入或者不加入，不需要for循环，这里为统一就写{f[i] = i;if(Constraint(t) && Bound(t))//满足约束dfs(t);//下一个位置}
}//以0-1背包为模板

void dfs(int t)                  //层号
{if(t > n)                    //递归结束output(x);elsefor(int i = t;i <= n; i++)    //扩展子节点{Swap(f[t],f[i]);            //记录if(constrain(t))dfs(t + 1);           //进入递归swap(f[t],f[i]);//回溯}
}//以八皇后问题为模板

分支限界法（广度优先搜索）

基本思想 ： 以广度优先搜索的方式搜索问题的解空间树，在搜索过程中，每一个节点只有一次机会扩展结点，每次扩展就扩展所有子节点，之后排除重复的和不可行的节点，其余节点加入节点队列中，之后从队首取出节点再次扩展，重复直至不满足条件

一般模式

void bfs()
{while(!q.empty()){//取出节点unode u = q.front();q.pop();//扩展ufor(int i = 0; i < n; i++){if(canMove(u,i)){v = moveto(u, i);}used[v] = 1;step[v] = step[u] + 1;q.push(v);}}
}

贪心算法

基本思想 ： 贪心算法总是做出当前看来最好的选择，不从整体上考虑，只是考虑局部最优解，即贪心选择

基本步骤：

从问题的初始解出发，采用循环语句，当可以向目标更进一步，根据局部最优策略，得到一个局部最优解缩小规模

将所有的局部最优解合并起来得到问题的最优解

• 无后效性 ： 某阶段的状态一旦确定，此后状态的演变不受之前状态的影响
• 最优子结构 ： 原问题的最优解包含子问题的解也是最优的

各算法思想的比较

备忘录算法【记忆化搜索】和普通dp

• 都是dp ，也就是都是要使用数组表记录计算问题的解

• 【区别】备忘录算法也就是之前 所讲的记忆化搜索，因为普通的递归往往会出现重复的子问题重复解决，所以就使用一个数组表格来记录使用情况，往往是依赖深搜的结果，也就是自顶向下；而普通dp是从最小子问题开始的，也就是自底向上 ---- 分析斐波拉契数列就知

分治法和dp

• 分治法和dp的基本思想相同，都是要把原问题分解成规模较小的子问题，解决子问题，得到最优解
• 【区别】分治算法子问题之间是相互独立的，不会共享底层子问题，子问题不是重叠的，并且也不会记录已经计算的状态；而dp的子问题则是重叠的，不独立，前一阶段的子问题为后一阶段的子问题提供信息，并且会记录已经计算的状态

dp和贪心

• 分治法和dp都要求最优子结构性质，无后效性
• 【区别】 贪心算法直接由局部最优解推到全局最优解，直接推导，所以上一步做出的选择不能保留，而递归则会使用数组表来记录上一步所记录的所有可能的解。普通dp通常自底向上解决问题，而贪心算法通常自顶向下，以迭代的方式来做出相应的选择，简化问题的规模。

回溯 和分支限界法

• 都是进行搜索，并且都是自顶向下
• 回溯法的搜索方式是深搜，分支限界法的搜索方式为广度优先，主要区别在于子节点的扩展方式不同
  • 回溯法：活结点的所有可行子节点都遍历完之后才会从栈中弹出
  • 分支限界法：每一个节点都只有一次机会成为活结点，一次性扩展所有可行子节点，并从队列中弹出

题目的分析

渐近时间

判断函数中渐近时间最小的

n + nlogn 2n + nlogn n^2 -logn n + 100logn

忽略系数，找到次数最高项， 第一个函数为O(nlogn) ,第二个为O(nlogn) ,第三个为O(n^2),最后一个为O(logn)

最优子结构

最优子结构是动态规划问题和贪心算法所具有的特点 ，含义就是原问题的最优解包含子问题的最优解

贪心算法不从整体上加以考虑，只是得到局部最优解，对于0-1背包就不能使用贪心算法

判断算法复杂度

void fun()
{for(int i = 0; i < n; i++){for(int j = i; j < n; j++){s++;}}
}

从带码中可以看出，频度最大的s++ ， 执行次数为 n + …… +1,也就是 (n + 1)n/2; 使用渐近时间表示为O(n^2)

整体分析

动态规划，回溯，分治，还有贪心；与递归技术联系最弱的是贪心 ； ---- 动态规划的备忘录算法是递归

• 动态规划的基本思想和要素
• 分支限界法的一般模式
• 回溯算法的子集树模式

算法题

考试为试卷，不是机考，因此要求手写代码，接下来，分析几个题，并附上代码，一定要理解，否则考试的时候写不出来的。

二分查找

bool binarySearch(int* arr, int num, int target)
{int low = 0;int high = num - 1;while (low <= high){int mid = low + (high - low) / 2;if (arr[mid] < target){low = mid + 1;}else if (arr[mid] > target){high = mid - 1;}else{return true;}}return false;
}

这段代码是很简单的，注意的点就是开闭

活动安排

该题使用的是贪心算法，贪心策略为每次都找结束时间最早的活动，所以就只需要按照结束时间排序，每次都选择结束时间最早的活动，这样子规模就不断缩小了

struct node {int begin;int end;
};node act[1001];int arrange(int n)
{int count = 1;int curend = 0;//上一个活动的结束时间for (int i = 0; i < n - 1; i++)//选择排序{for (int j = 0; j < n - i - 1; j++)//按照结束时间的早晚排序{if (act[j].end > act[j + 1].end){node temp = act[j];act[j] = act[j + 1];act[j + 1] = temp;}}}curend = act[0].end;for (int i = 1; i < n; i++)//第一项已经选择了{//和已经参加的活动的结束时间比较if (act[i].begin >= curend){//选择该活动curend = act[i].end;count++;}}return count;
}

前面就一个排序的代码，这里可以明显看出具有无后效性，还有最优子结构；这里安排0 - 24时的活动，那么对于子问题2 - 24时的活动就不需要考虑前两个小时的活动安排了，如果子问题时最优解，那么原问题就是 1 + 子问题最优解，所以具有最优子结构

之前发的有点问题，所以撤回了~