算法基础+分治策略(算法复习第1弹)

马上就要算法考试了,好紧张,先复习第一波....

参考文献(算法导论)+(张莉老师ppt)


函数的增长,对算法效率的描述

渐进记号:Θ、Ω、O、o、w(那个很像w的符号,不记得咋打出来了)

Θ标记(最常用):存在正常量c1和c2,使得当n 足够大的时候,能够让函数 f(n) 夹入c1g(n)和c2g(n)之间

如图:

f(n)=Θ(g(n)) 图一

称g(n)是f(n)的一个渐进紧确界,也就是f(n)得在c1g(n)和c2g(n)之间,不得越界

举个例子证明(考点):

证明这个式子

图二

Ω标记:渐进下界

如图,和图一相比,它没有上界要求,图一上下均不能越界,它只有下界要求,所以叫做渐近下界

图三

O:渐近上界

和Ω标记类似,上边不越界,下边不做要求

图四

o标记:非渐进紧确的上界,图一Θ是渐进紧确的,而O可以是Θ

也可以不是,而o有点像集合中真包含的概念,它不是Θ的O

w(那个很像w的符号,不记得咋打出来了)标记符:和o相反,非渐进紧确的下界

通过上边几个图的理解,下边表里边的式子就很好理解了

左边是满足的表达式,右边是两者的相对增长速度

图五

这也是比较两个函数之间增长速度的方法(n足够大的时候,求函数之比的极限,根据结果判断)

图六


分治策略

概念:将原问题分解成子问题,子问题与原问题一样,至少规模更小,直到规模足够小,递归停止,问题得以解决

包括的例子有,归并排序、实验中的gray码问题

分治算法的分析:

分治法解题的一般步骤

(1)分解,将要解决的问题划分成若干规模较小的同类问题;

(2)求解,当子问题划分得足够小时,用较简单的方法解决;

(3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。

三个求解分治法Θ或Ω的方法

1、代入法

即假设一个界,然后数学归纳法证明

这种方法需要经验的积累,可以通过转换为先前见过的类似递归式来求解。

2、递归树法

在递归树中,每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合,再将每层的代价相加得到递归式所有层次的总代价。

如归并排序,忘了归并排序的可以参照这里  归并排序

这是其递归式

图七

这是递归树的式子(主方法常用这个式子)

图八

递归树式子需要解释的地方有

cn其实就是一个函数f(n),这个函数所代表的意思是分解和合并步骤所花费的时间,哈哈

其(f(n))复杂度为Θ(n),由此再去理解图七中的式子就好理解了

下面来用递归树的方法求分治算法的渐进界:

下边这是ppt上的例子,怎么理解这个递归树例子呢,最顶层是cn,从它开始递归,首先你可以把n理解为2的某次幂,比如,n是2的4次幂,所以整个递归树就有(logn)也就是4层,每一层的代价刚好都是cn,可求出其T(n),第5层也就是常量的,为Θ(n),也可以回去图八和图七解释,哈哈

图九

这个例子也一样,只不过不是递归成一样的问题,是两个一样的子问题

图十

3、主方法法

它可以瞬间估计一个递推式的算法复杂度。但是我们知道,这后面肯定是严格的数学证明在支撑着,对于我们用户来说,我们只用知道怎么用就行了。

T(n) = aT(n/b) + f (n) ,函数f(n),这个函数所代表的意思是分解和合并步骤所花费的时间

下图就是主定理,记住就行,也可以自己去推导一蛤~

图十一

PPT上这样说主定理,一样的

图十二

图十三

下面贴一段gray码问题的分治解法


图十四

第一次写简书,写的乱乱的,明天将推出动态规划和毛概,希望写的更好,祝大家期末取得好成绩~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏常用编程思想与算法

常用编程思想与算法

本文是在阅读Aditya Bhargava先生算法图解一书所做的总结,文中部分代码引用了原文的代码,在此感谢Aditya Bhargava先生所作出的这么简单的...

2051
来自专栏后端技术探索

两道腾讯技术面试题(二面经历)

编程语言不限,主要考查两方面能力:1.算法逻辑能力。2.编码能力。笔者上次换工作,面试了十余家公司,其实很多关于算法逻辑的面试题都大同小异,每遇到一道题目就吃透...

1052
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

4355
来自专栏落影的专栏

程序员进阶之算法练习(四)

前言 我认为的编程能力: 基础知识:数据库、操作系统、网络原理等; 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)等;...

45810
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

5029
来自专栏aCloudDeveloper

算法导论第九章中位数和顺序统计量(选择问题)

  本章如果要归结成一个问题的话,可以归结为选择问题,比如要从一堆数中选择最大的数,或最小的数,或第几小/大的数等, 这样的问题看似很简单,似乎没有什么可研究的...

3357
来自专栏木可大大

算法初体验

在介绍具体算法之前,我先谈一下个人对学习算法的初心。我的初心无非有两点:一,BAT等互联网公司招聘面试时要问算法知识,如果想要进入互联网公司,我就必须学好算法;...

843
来自专栏落影的专栏

程序员进阶之算法练习(十九)

前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

3776
来自专栏IT可乐

Java数据结构和算法(一)——简介

  本系列博客我们将学习数据结构和算法,为什么要学习数据结构和算法,这里我举个简单的例子。   编程好比是一辆汽车,而数据结构和算法是汽车内部的变速箱。一个开车...

3129
来自专栏zaking's

js算法初窥05(算法模式02-动态规划与贪心算法)

2053

扫码关注云+社区

领取腾讯云代金券