《大话数据结构》读书笔记——第2章 算法
发布日期:2021-07-01 02:29:54
浏览次数:2
分类:技术文章
本文共 861 字,大约阅读时间需要 2 分钟。
第2章 算法
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
2.5 算法的特性
特性 | 理解 |
---|---|
输入、输出 | 算法具有零个或一个输入、一个或多个输出 |
有穷性 | 算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成。 |
确定性 | 算法的每一步都有确定的含义,无二义性 |
可行性 | 算法的每一步都可行,每一步都能通过执行有限次数完成 |
2.6 算法的设计要求
要求 | 理解 |
---|---|
正确性 | 算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案 |
健壮性 | 当输入不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。 |
可读性 | 便于理解和交流 |
效率和存储量 | 时间效率高和存储量低 |
正确性的四个层次:
- 没有语法错误
- 正确的输入有对应结果
- 非法的输入能够得到满足规格说明的结果
- 对应精心选择的,甚至刁难的测试数据有满足要求的输出结果
2.7.2 事前分析估算法
- 在计算机程序编制前,依据统计方法对算法进行估算
2.9 算法的时间复杂度
- 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而进行分析T(n)随n的变化情况并确定T(n)的数量级。
2.9.2推导大O阶法
- 用常数1取代运行时间中的所以加法常数
- 在修改后的运行次数函数中,只保留最高阶项。
- 如果最高阶存在,且不是1,则去除这个项相乘的常数,得到的结果就是大O阶。
2.10常见的时间复杂度
O(1)<O(logn)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
总结
1.如何记忆算法基本特性及设计要求:
- 首先要有0个或1个输入,满足确定性,保证语句不存在二义性,并且每一步都可行,可以在一定时间内(有穷)完成,最后输出;
- 设计的要求
- 正确是基础,健壮、可读不能忘,效率存储需优化。
- 函数的渐近增长
给定两个函数f,g,如果存在一个整数n,使得在大于n时,f总比g大,那么,我们说f的增长渐近快于g。
转载地址:https://matches999.blog.csdn.net/article/details/90609565 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月19日 12时34分37秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
当博士进入币圈会怎么样
2019-05-01
委员会怎么验证比特币真伪
2019-05-01
PHP之 使用PHPMailer插件实现邮件发送功能
2019-05-01
《增长黑客》(肖恩·艾利斯)学习笔记——第二部分 实战
2019-05-01
python使用HTMLTestRunner查看运行函数
2019-05-01
python的ImportError
2019-05-01
linux下安装jenkins+git+python
2019-05-01
windows10家庭版开启组策略
2019-05-01
解决uiautomatorviewer中添加xpath的方法
2019-05-01
性能测试的必要性评估以及评估方法
2019-05-01
Spark学习——利用Mleap部署spark pipeline模型
2019-05-01
Oracle创建表,修改表(添加列、修改列、删除列、修改表的名称以及修改列名)
2019-05-01
使用redis实现订阅功能
2019-05-01
URL特殊字符转码
2019-05-01
对称加密整个过程
2019-05-01
java内存模型
2019-05-01
volatile关键字
2019-05-01
tomcat_关闭
2019-05-01
Servlet_快速入门
2019-05-01