算法相关

算法 学习笔记

2017-05-17  本文已影响1454人  卡尔是正太

算法 Algorithm

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制

只有在后启示录世界，所有连接到互联网的计算机的硬盘都被炸了，所有基础学术论文和计算机科学教科书都化为灰烬，你才真正需要记住算法。

尝试理解并思考算法的本质,尝试去实现每一个你不论多糟糕的想法,尝试去向更为优秀的算法

算法基础概念

a←b  \\ 语句的含义是将b的值赋给a。

这里a是变量、数组项，b是算术表达式、逻辑表达式或指针表达式
变量交换

a<->b

若a和b都是变量、数组项，那么记号a<->b 表示a和b的内容进行交换。

if i=10
      then xxxx
      else xxxx                 //else 和 then 要对齐
if i=10
      then xxxx                   //if 后面必定跟上then，else后面不用跟then
      elseif i=9                  //elseif 要连在一起写
      then xxxx
        yyyy
    else  xxxx             //else 跟在elseif 的 then 对齐

while time<10
      do  xxxxx                  //while后面必定要紧跟缩进的do
      xxxxx
      end

for

for var init to limit by incr do
      xxxx
end
for i←0 to 10        //for、while、if 后面的条件语句都不用加括号
    do ...                 //for后面必定要紧跟缩进的do
    ...

这里var是变量，init、limit和incr都是算术表达式，
而xxxx是由一个或多个语句组成的语句串。
初始时，var被赋予init的值。假若incr≥0，则只要var≤limit，就执行s并且将incr加到var上。
（假若incr<0，则只要var≥limit，就执行s并且将incr加到var上）。incr的符号不能由xxxx来该改变。

search（A，name） //参数类型可以不给出，但必须在注释中说明

算法基础概念

数学基础

函数的渐近的界
利用极限求函数渐近的界
有用的求和级数及推导方法
基本效率类型

算法分析实例

非递归形式算法分析
递归形式算法分析(难点)

递推法分析时间复杂度 求n!

递推法分析时间复杂度 汉诺塔问题

主定理

主定理(Master Theorem) 设a≥1, b＞1为常数，f(n)为函数，T(n)为非负整数，且 T(n)=aT(n/b)+f(n) 则有以下结果

迭代法

是一种不断用变量的旧值递推新值的过程

杨辉三角

杨辉三角

斐波那契数列

f(n) = f(n-1)+f(n-2)

内存移动问题

数组中有n个数据，要将它们顺序循环向后移k位，即前面的元素向后(右)移k位，后面的元素则循环向前移k位 后面的元素则循环向前移k位，例：0、1、2、3、4、5循环移3位后为： 3、4、5、0、1、2。考虑到n会很大，不允许用2n及以上个空间来完成此题*
解题思路 : 利用移动长度与数据个数的关系约简运算

内存移动

求解方程的近似算法 （以9x2-sin x-1=0为例）

线性代数方程组

线性代数方程组有如下特征

线性规划问题

研究线性约束条件下线性目标函数的极值问题的数学理论和方法

蛮力法/暴力法

直接基于问题的描述和所涉及的概念定义的进行算法设计，简单而直接。

枚举法

利用枚举所有的情况，或者其它大量运算又不用技巧的方式，来求解问题的方法。

穷举查找

图的搜索

分治法

把一个较大的问题分解成几个与原问题相似的子问题，找到求出这几个子问题的解法后，再以适当的方法组织，把它们合成求整个问题的解法。

二分查找

思路：将按顺序排列元素拆分成更小的集合来查找
将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。如果x=a[n/2]，则找到x，算法终止。如果x<a[n/2]，则在集合的前半部分继续查找，否则在后半部分查找。

大数乘法

思路：将大数X分解成登场的两部分 X0 X1 例如

分解
计算模型
将两个大数字的乘法分解成了四个较小数字的乘法
计算模型公式
此思路下的时间复杂度为
迭代时间复杂度
根据主定理求得时间复杂度
此时，对计算模型公式进行进一步优化可以将四个乘法操作简化到三个
新计算模型公式
继续求得时间复杂度
新计算模型公式时间复杂度
伪代码描述
伪代码描述

Strassen矩阵乘法

将两个矩阵的乘法转化为两个矩阵四个区域相乘的结果，如果区域内只剩下一个数字，此时矩阵乘法就变成了简单的数字相乘，见下图

矩阵分解
或者根据Strassen方程 进行更快速的运算
Strassen方程[?]算法
(1)划分(Divide)：把矩阵A和B划分为(n/2)*(n/2)的子矩阵，完成加减运算，求解Mi(递归)
(2)运算(Conquer)：按Strassen方程，执行7个(n/2)*(n/2)的子矩阵乘法运算
(3)合并(Combine)：按Strassen方程，通过加减运算求C

棋盘覆盖问题

选择性问题 （选最大值、最小值、选中位数、选第二大值）

贪心算法

是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
贪心算法的难度是对选择正确性的证明

教室分配问题

struct Active{
                startTime   s;  //活动开始时间
                endTime     e;  //活动结束时间
                selectflag  f;  //选标识 
                    }A[n];

(2)计算：活动i与活动j相容A[i].s≥A[j].e或A[j].s≥A[i].e
用归并排序或其他任何高效的排序算法完成以
a[i].e的从小到大的排序，形成序列
A[1].e≤A[2].e ≤…≤A[n].e

数列极差问题

给定含有n个正整数的数列a，做如下两步操作：
(1)每一次删除其中的两个数ai和aj;
(2)在数列中加入一个数ai×aj+1，
循环执行步骤(1)(2)直到集合中只剩下一个元素为止。设计算法求得数列中剩余的数为最大值max和最小值min，则该数列的极差为M=max-min。

当一个数列中含有n(n>2)数时，该数列按数列极差法求最大数值的方法为：每次选择数列中最小的两个数进行相乘加1。求最小数值为：每次从数列中选择两个最大的数相乘加1

(1) 当k=3时，数列a={a1, a2, a3}，不妨令a1< a2< a3，这样可以设a2= a1+k1 (k1>0)；a3= a1+k1+k2(k1,k2>0)。那么这三个数的三种组合方式为：
(a1* a2+1)* a3+1
= a1* a1* a1+(2k1+k2) a1 a1 +(k1(k1+k2)+1)a1+k1+k2+1
(a1 a3+1)* a2+1
= a1* a1* a1+(2k1+k2) a1 a1 +(k1(k1+k2)+1)a1+k1 +1
(a2 a3+1)* a1+1
= a1* a1* a1+(2k1+k2) a1 a1 +(k1(k1+k2)+1)a1 +1
类比上述三式的同类项，可知命题成立
(2)假设k=n时命题成立。为了方便运算，不妨设{a1,a2,…,ak}为任意顺序的组合，[ai aj]= aiaj +1，则数列a的最大极值
{an}max=[ a1 a2…an], a1<a2…<an 。
证明k=n+1成立，也就是证明{an+1}max=[ a1 a2…an an+1]。还可以表示为
{an+1}max=[[ a1 a2…an], an+1]= [ a1 a2…an]* an+1+1。
为了证明k=n+1成立，我们需要先证明一个引理。（略）

最优装载问题

有一批集装箱准备装上轮船，编号依次为1, 2, …, n，其中集装箱i的重量是wi，i=1, 2,…, n。已知轮船最多装载量是C，每个集装箱的重量wi≤C，且对集装箱无体积限制，设计算法求如何选择能够使得装上的集装箱个数最多。

数字串删除问题

键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。对给于定的N和S，寻找一种方案使得剩下的数字组成的新数最小。
输出：包括所去掉数字的位置和组成的新正整数

近似贪心问题

动态规划

与分治算法类似，动态规划算法也是将待求解问题分解成若干个子问题，分阶段求解子问题，前一阶段子问题的解成为求后续阶段子问题的解的计算信息，最后用这些子问题的最优解构造出原问题的最优解。

与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法来解这类问题，则分解得到的子问题数目太多，且相互重叠，以至于解决原问题时间渐近复杂度为指数级。然而，不同子问题的数目常常只有多项式量级，且有些子问题被重复计算了许多次。如果能够保存已解决子问题的解，需要时直接使用，从而减少重复计算，就要可以得到多项式时间的算法。

子问题重叠
问题本身是可分解的，而且分解出来的子问题之间并不是独立的，存在重叠的部分。这个性质表现在两个方面：
①一个子问题的解可能与另一个子问题的解存在重复的部分；
②多个子问题的解在下一阶段决策中，可能被多个延续子问题多次使用。

子问题的解为下一阶段的求解提供帮助

最优子结构
当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法求解的一个关键特征。

动态规划设计的基本步骤 **
1 找出最优解的性质，并刻画其结构特征。
2 按最优解的性质，划分子问题及演算的阶段，建立递推方程。
3 以自底向上或自顶向下的记忆化方法(备忘录法)计算出最优值。
4 根据每阶段推算出的局部最优解，构造出全局最优解。

数塔问题

data[n][n]     \\存储原始数据信息；
r[n][n]        \\存储每一阶段的路径的计算结果；
path[n][n]     \\存储下一步最优结点列坐标。

计算：阶段性最优
r[i][j]=max{r[i+1][j], r[i+1][j+1]}+data[i][j] i=n-2,…,1; j≤I
下一最优子结点的列坐标


最优解 data[1][1]data[2][j]data[i+1][j]……，i= j=1，j=j+path

投资分配问题

概率算法

利用数据序列的随机性和概率分布等特点，设计解决问题的算法或提高已有算法的效率

随机性(randomness)
某一事件集合中的各个事件所表现出来的不确定性。可能遵循某个概率分布

随机序列(random sequence)/随机变量序列
如果用X1，X2……Xn代表随机变量，这些随机变量如果按照顺序出现，就形成了随机序列。
(1) 序列中的每个变量都是随机的；
(2) 序列本身就是随机的。

随机数

蒙特卡洛算法

蒙特卡洛方法（Monte Carlo method），也称统计模拟方法，随机化算法的种类之一是1940年代中期由于科学技术的发展和电子计算机的发明，而提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。
与它对应的是确定性算法[?]
蒙特卡洛方法在金融工程学，宏观经济学，生物医学，计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。

蒙特卡洛算法的特点

蒙特卡罗算法在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体的解是否正确。

蒙特卡洛算法进行数值计算

计算圆周率π

蒙特卡洛算法进行素数判定

#define range 2000
bool IsPrime[range+1];
//set函数确定i是否为素数，结果储存在IsPrime[i]中 
void set(bool IsPrime[])
{
      int i,j;
      for(i=0;i<=range;++i)
      IsPrime[i]=true;
      IsPrime[0]=IsPrime[1]=false;
      for(i=2;i<=range;++i)
      {
            if(IsPrime[i])
            {
                  for(j=2*i;j<=range;j+=i)
                  IsPrime[j]=false;
            }
        }
}

舍伍德算法

舍伍德算法是概率算法的一种，该文在比较线性表的顺序存储与链式存储的特点之后，提出了一种较优的数据结构——用数组模拟链表。理论上证明了采用舍伍德算法进行查找运算的时间复杂度为0(n)，并在计算机上给出相应数据的模拟。

舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。

以快速排序为例分析舍伍德算法

快速排序即是一种最坏情况与平均情况差距较大的算法

拉斯维加斯算法

随机生成答案并检测

算法思想：用随机序列代替有规律的枚举，判断枚举随机结果是否正确。
特征：得到的解都是正确的，但是有时找不到解。求得正确解的概率也依赖于算法所用的时间。
原理：通常采用bool型方法来表示拉斯维加斯算法。当算法找到一个解时返回true，否则false。当返回false时，说明未得到解，那么可再次独立调用该算法，在时间允许的情况一直运算到出解为止。

n皇后问题

上一篇 下一篇

猜你喜欢

热点阅读