首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
zzzzzxf
获赞
3
粉丝
5
关注
0
看过 TA
1
南京大学
2019
算法工程师
IP属地:江苏
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑zzzzzxf吗?
发布(5)
刷题
zzzzzxf
2018-12-16 18:26
算法工程师
【有书共读】《算法导论》第4章 - 分治策略 读书笔记(下)
用代入法求解递归式 分为两步: 猜测解的形式 用数学归纳法求出解中的常数,并证明解是正确的 用递归树方法求解递归式 在递归树中,每个结点表示一个单一子问题的代价,子问题对应某次递归函数调用。 我们为递归式T(n) = 3T(⌊n/4⌋) + Θ(n2)创建一棵递归树: 整棵树的代价就是所有层次的代价之和。 用主方法求解递归式 主方法可以直接求解如下形式的递归式:T(n) = aT(n / b) + f(n) 主方法依赖于主定理:
0
点赞
评论
收藏
转发
zzzzzxf
2018-12-02 19:15
算法工程师
【有书共读】《算法导论》第4章 - 分治策略 读书笔记(中)
矩阵乘法的Strassen算法 若A=(aij)和B=(bij)是n×n的方阵,则对i,j=1,2,3,…,n,定义乘积C=A•B中的元素cij为: 我们很容易得到一个执行时间为Θ(n3)的算法来计算矩阵乘法,因为矩阵乘法的的自然定义就需要进行这么多次的标量乘法。然而实际上,我们有方法在o(n3)时间内完成矩阵乘法:Strassen的著名n×n矩阵相乘的递归算法。后面它将被证明运行时间为Θ(nlg7)——渐近复杂性优于简单的矩阵乘法过程。 一个简单的分治算法 假定将A、B和C均分解为4个n/2×n/2的子矩阵: 因此可以将公式C=A•B改写为: ...
0
点赞
评论
收藏
转发
zzzzzxf
2018-12-02 16:49
已编辑
算法工程师
【有书共读】《算法导论》第4章 - 分治策略 读书笔记(上)
在分支策略中,我们递归地求解一个问题,在每层递归中应用入下三个步骤: 分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。 解决步骤递归地求解出子问题。如果子问题的规模足够小,则停止递归,直接求解。 合并步骤将子问题的解组合成原问题的解。 当子问题足够大,需要递归求解时,我们称之为递归情况。当子问题变得足够小,不再需要递归时,我们说递归已经“触底”,进入了基本情况。 使用递归式可以很自然地刻画分治算法的运行时间。一个递归式就是一个等式或不等式,它通过更小的输入上的函数值来描述一个函数。例如用递归式描述归并排序过程的最坏情况...
0
点赞
评论
收藏
转发
zzzzzxf
2018-11-25 16:36
已编辑
算法工程师
【有书共读】《算法导论》第3章 - 函数的增长 读书笔记
当输入规模足够大,使得只有运行时间的增长量级有关时,我们要研究算法的渐进效率。 渐近记号 Θ记号 Θ记号渐近地给出一个函数的上界和下界。对一个给定的函数g(n),用Θ(g(n))来表示以下函数的集合: 值得注意的是,我们通常会用这样一种方式活用等式:用“f(n) = Θ(g(n))”表达与"f(n) ∈ Θ(g(n))"相同的概念。 对于所有n≥n0,如果函数f(n)在一个常量因子内等于g(n),我们称g(n)是f(n)的一个渐近紧确界。 Ο记号 当只有一个渐近上界时,使用Ο记号。对于给定的函数g(n),用Ο(g(n))...
0
点赞
评论
收藏
转发
zzzzzxf
2018-11-25 16:36
已编辑
算法工程师
【有书共读】《算法导论》第1、2章读书笔记
第1章 第1章内容是此书的导读章节,所以在此只对一些第一次出现的必要的概念和有助于理解此书的段落进行摘抄或总结。 算法:非形式地说,算法(algorithm)就是任何良定义的计算过程,该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样,算法就是把输入转换成输出的一个计算步骤的序列。 数据结构:数据结构是一种存储和组织数据的方式,旨在便于访问和修改。 虽然可以把本书当做一本有关算法的“菜谱”来使用,但是也许在某一天你会遇到一个问题,一时无法很快找到一个已有的算法来解决它。所以本书将教你一些算法设计与分析的技术,...
0
点赞
评论
收藏
转发
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务