3 刘洋洋

华中科技大学 机械工程

Java服务端研发,喜欢底层原理与基础算法设计

等级
TA的排名 4k+

【算法设计与分析】16 分治策略:快速排序(快速排序的时间复杂度计算)

上一篇文章学习了:【算法设计与分析】15 分治策略:芯片测试文章目录1. 快速排序的基本思想1.2 时间复杂度的计算1.21 最坏情况时间复杂度计算1.22 最好情况时间复杂度1.23 平均时间复杂度计算2 总结1. 快速排序的基本思想用首元素 x 作划分标准,将输入数 组 A划分成不超过 x 的元素构成的数 组 AL,大于 x 的元素构成的数组 AR. 其中 AL, AR从左到右存放...

2019-10-27 00:19:11

【算法设计与分析】15 分治策略:芯片测试

上一篇文章学习了【算法设计与分析】14 分治算法的一般描述和分析方法文章目录1. 芯片测试1.1 一次测试的过程1.2 如何测试一块芯片的好坏1.3 蛮力算法1.4 分治算法设计思想1.41 分治算法的正确性证明1.42 时间复杂度分析2. 总结本篇文章借助具体的例子来学习分治策略。这个例子是课本上的:芯片测试的例子。1. 芯片测试在讲解具体的芯片测试的分治策略算法之前,先来了芯片测试...

2019-10-13 00:47:24

idea_取消自动import .*

打开设置 > Editor > Code Style > Java > Scheme Default > Imports① 将 Class count to use import with “" 改为 99 (导入同一个包的类超过这个数值自动变为 * )② 将 Names count to use static import with "” 改为 99 (同上,但...

2019-10-11 14:22:33

【算法设计与分析】14 分治算法的一般描述和分析方法

本文主要描述分治算法的一般描述和分析方法。衔接上一篇文章:【算法设计与分析】13 分治策略的设计思想文章目录1 分治算法的一般性描述1.1 分支算法的时间分析1.2 两类常见的递推方程与求解方法2 总结1 分治算法的一般性描述设分治算法为:Divide-and-Conquer§设计要点原问题可以划分或者规约为规模较小的子问题。其中子问题之间遵循以下的规则: 1. 子...

2019-09-28 15:25:49

【算法设计与分析】13 分治策略的设计思想

算法中很多方法都是可以采用分治策略进行设计与优化,那么什么是分治策略?如何使用分治策略进行算法的设计与分析?文章目录1. 分治策略的基本思想1.1 二分检索的设计思想1.2 二分归并排序的设计思想1.3 Hanoi塔的递归算法2 小结1. 分治策略的基本思想分治策略(Divide and Conquer)将原始问题划分或归结为规模较小的子问题递归或者迭代的求解每个子问题将子问...

2019-09-28 13:49:07

单元测试debug过程中,显示variables are not available

注:我的代码是多线程异步执行的单元测试,代码在进行debug调试时,执行到某一行代码突然就显示variablesarenotavailable,多次尝试,始终是会在某一行代码处出现上述的情况。经过分析,得出原因:单元测试的过程中,会kill掉执行的线程,所以使用单元测试,如果是多线程模式,很难调试。改变测试方法:将所测试的接口,在Controller层转调,然后启动项目(D...

2019-09-24 22:20:57

【算法设计与分析】12 主定理及其应用

主定理是一个非常有用的定理,前面我们学习的所有知识都可以用主定理来求解,而不必要使用复杂的计算方法来求解文章目录1. 主定理1.1 主定理的应用背景1.2 主定理内容2. 主定理的应用2.1 求解递推方程 例12.2 求解递推方程 例22.3 求解递推方程 例33. 总结1. 主定理1.1 主定理的应用背景求解递推方程:T(n) = a T(n/b) + f(n)其中:a: 归...

2019-09-15 21:50:03

【算法设计与分析】11 递归树

当前面所学习的迭代法、差消法等不太好解决的问题,可以使用递归树,来很方便的解决。文章目录1. 递归树的概念1.1 迭代在递归树中的表示2. 递归树的生成规则2.1 递归树生成实例2.2 递归树应用实例3. 总结1. 递归树的概念递归树是迭代计算的模型递归树的生成过程与迭代过程一致递归树上的所有项恰好是迭代之后产生的和式中的项对递归树上的项求和,就是迭代后方程的解1.1 迭代在...

2019-09-15 21:18:57

【算法设计与分析】10 差消法化简高阶递推方程

上一篇文章使用递推方程的方法求解了插入排序和二分归并的时间复杂度,本文来求解快速排序的时间复杂度,同样是利用了递推方程法,但是求解该递推方程的方法与以前不一样:差消法文章目录1. 快速排序的时间复杂度求解2. 总结1. 快速排序的时间复杂度求解这里求解的是快速排序的平均时间复杂度,并非求解的是最坏情况时间复杂度,为什么?想想上一篇文章,都是可以很容易的列出求解时间复杂度的递推式子。...

2019-09-15 20:46:03

【算法设计与分析】09 递推方程与算法分析

关于什么是递推方程,这里就不再多说了。本文主要讲讲简单的递推方程来求解算法的时间复杂度文章目录1. 递推方程的引入1.1 插入排序时间复杂度求解1.2 二分归并排序时间复杂度求解2 总结1. 递推方程的引入汉诺塔问题大家都知道,现在以汉诺塔问题来引入递推方程,可以参考文章离散数学中的数据结构与算法】十 汉诺塔我们知道汉诺塔的递归算法对应的递推式子为: T(n) = 2 T(n-1...

2019-09-15 20:07:39

【算法设计与分析】08 序列求和的方法

本篇文章学习数列求和的一些方法。这些方法对后面学习算法的时间复杂度非常有帮助。文章目录1. 数列求和公式1.1 二分搜索的时间复杂度求解2 估计和式上届的放大法3 估计和式渐近的界4 总结1. 数列求和公式下面这几个数列求和公式都是高中学过的公式。等差、等比数列和调和级数下面给出一个求和的例子,使用了一些高中都会的变换的技巧:学习上面的公式,主要是为了解决算法的时间复杂度,...

2019-09-15 14:46:51

【算法设计与分析】07 算法的数学基础

接下来的几篇文章将是学习算法的数学基础内容。具体的文章包括(持续更新):

2019-09-15 10:38:59

【算法设计与分析】06 几类重要的函数

本篇文章中会用到上一篇文章的定理:【算法设计与分析】05 有关函数的渐进的界的定理主要学习常见的一些函数的阶1. 基本函数类以下按阶的高低排序:至少指数级: 2n, 3n, n!, …多项式级: n, n2, nlogn, n1/2, …对数多项式级: logn, log2n, loglogn, …1.1 对数函数算法中常用的符号:性质:下面对上面的性质进行证明:...

2019-09-14 23:38:11

【算法设计与分析】05 有关函数的渐进的界的定理

上一篇文章学习了函数的渐近的界定义,本篇文章继续学习函数渐近的界定理。这些定理的证明,用到了函数渐近的界的定义。点击查看上一篇文章:【算法设计与分析】04 函数的渐进的界文章目录1. 定理11.1 证明定理11.2 估计函数的阶1.3 一些重要的结论1.31 多项式函数的阶低于指数函数的阶1.32 对数函数的阶低于幂函数的阶2. 定理22.1 例子3. 定理34. 总结1. 定理1定理:...

2019-09-14 18:53:22

aop编程时出现错误信息:java.lang.NoClassDefFoundError

代码错误信息:org.springframework.beans.factory.BeanCreationException: Error creating bean with name ‘calImpl’ defined in file [/Users/lyy0217/Downloads/SSM/target/classes/com/cm/service/aop/CalImpl.class]:...

2019-08-25 22:03:52

通配符的匹配很全面, 但无法找到元素 'mvc:annotation-driven' 的声明

报错信息:通配符的匹配很全面, 但无法找到元素 'mvc:annotation-driven' 的声明原因是:虽然在xml文件上方声...

2019-07-15 22:56:47

【算法设计与分析】04 函数的渐进的界

今天学习函数的渐进的界,会涉及多种数学符号。对以后学习分析算法复杂度有很大的帮助。1 大OOO符号定义: 设 f 和 g是定义域为自然数集N上的函数. 若存在正数 c 和 n0, 使得对一切 n ≥\geq≥ n0有:c≤f(n)≤cg(n)c\leq f(n) \leq cg(n)c≤f(n)≤cg(n)成立。则称f(n)的渐近的上届是g(n)。记作:f(n)=O(g(n))f(n...

2019-06-29 23:54:34

【算法设计与分析】03 算法及其时间复杂度

在学习算法的时间复杂度之前,需要了解下面5条概念什么是算法的时间复杂度? 针对指定基本运算,计数算法所做的运算次数。什么是基本运算?比较、加法、乘法、置指针、交换…什么是输入规模?输入串的编码长度,通常是数组元素的多少、调度问题的任务个数、图的顶点数与边数等。算法的基本运算次数可以表示为输入规模的函数。给定问题和基本运算,就决定了一个算法类文章目录1 算法的两种时间复杂度1.1...

2019-06-29 00:39:02

Markdown编辑器 公式指导手册

#Cmd Markdown 公式指导手册标签: Tutorial2018-03-20 补档:收到很多小伙伴对本文的源文档转载需求,故传了一份 md 文件,请按需 下载 。本文固定链接: https://www.zybuluo.com/codeep/note/163962点击跳转至 Cmd Markdown 简明语法手册 ,立刻开始 Cmd Markdown 编辑阅读器的记录和写...

2019-06-28 19:13:52

【算法设计与分析】02 货郎问题与计算复杂性理论

什么是NP系列问题?今天来看看这些问题。1 货郎问题问题:有n个城市,已知任何两个城市之间的距离,求一条每个城市恰好经过1次的回路,使得总长度最小。建模与算法:输入:有穷个城市的集合C={c1,c2,…,cn},距离d(ci,cj)=d(cj,ci) ∈\in∈ Z+ ,1≤\leq≤i≤\leq≤j≤\leq≤n输出:1,2,…,n的排列k1,k2,…,kn,使得:...

2019-06-28 00:11:02

查看更多

CSDN身份
  • 博客专家
勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 脉脉勋章
    脉脉勋章
    绑定脉脉第三方账户获取
  • 推荐红人
    推荐红人
    发布高质量Blink获得高赞和评论,进入推荐栏目即可获得
  • 精彩红人
    精彩红人
    发布高质量Blink获得高赞和评论,进入精彩栏目即可获得
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。