导图社区 算法引论
算法引论知识总结,介绍了算法的概念,算法的表达,算法的复杂度分析,算法的设计步骤等,是计算机算法设计与分析的基础,为学习者日后掌握各种具体算法打下基础,是学习算法过程中不可不学的重要内容。
一步步教你构建一个股票模糊搜索框,涉及JavaScript学习、前端设计与编程、股票数据处理、Django网站搭建等各个方面的知识。强烈推荐计算机编程初学者参考尝试,有助于快速提高编程能力。
来自名牌大学博士生的书单推荐。涉及计算机科学、数学、复杂性科学、心理学、社会心理、生物学等等各个学科,帮助大家拓宽眼界,开拓视野,积累知识,走向成功人生。
本模板介绍了计算机学科学术论文检索与阅读的方法,非常适合希望提高学术能力的本科生和研究生学习。模板介绍了论文的相关名词解释、搜索工具、基本结构、阅读方法和原则等内容,有助于提高学生的学术科研能力。
社区模板帮助中心,点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
算法引论
算法的概念
算法的基本含义
求解一确定问题的某种方法
算法的定义
非形式化的描述
算法是有穷的合式规则集合,它规定了解决某一特定类型问题的一系列操作,是解决问题的方法或过程,是满足输入、输出、确定性、有限性的指令序列
输入:有零个或多个外部量作为算法的输入。
输出:算法产生至少一个量作为输出。
确定性:组成算法的每条指令清晰、无歧义。
有限性:算法中每条指令的执行次数有限,执行每条指令的时间有限。
算法与程序
程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)即有限性,如操作系统。
程序 = 编程语言 + 算法 + 数据结构
算法研究的范畴
数值计算
线性非线性方程,插值,积分微分
非数值计算
排序、优化、着色、路径、遍历、机器学习、数据挖掘
算法的性质
正确性
如果对任给的一个有效输入,算法总在有限时间内给出问题的正确答案,则称解算该问题的算法是正确的。
这里主要指算法的数学正确性。因为数学正确性是程序正确性的基础。在编制算法时,要给出正确性的数学证明。
工作量
用执行时长度量
依赖于具体的执行机器,不好
用基本操作次数度量
与执行的计算机无关
空间用量
除去程序和输入数据的存贮空间以外要用的空间
就地工作:额外空间用量是关于输入规模的常函数
简单性
算法应直观,清晰易读,一个简单的算法易于证明其正确性,也易于分析工作量
最佳性

表达算法的抽象机制
语言级抽象
高级程序设计语言
1.接近算法语言,易学、易掌握
2.为程序员提供了结构化程序设计的环境和工具,程序可读性好,可维护性强,可靠性高
3.不依赖于机器语言,程序可植性好、重用率高
4.编译程序处理琐碎事务,所以自动化程度高,开发周期短,程序质量高。
数据级抽象
抽象数据类型
抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算
优点
(1)算法顶层设计与底层实现分离;
(2)算法设计与数据结构设计隔开,允许数据结构自由选择;
(3)数据模型和该模型上的运算统一在ADT中,便于空间和时间耗费的折衷;
(4)用抽象数据类型表述的算法具有很好的可维护性;
(5)算法自然呈现模块化;
(6)为自顶向下逐步求精和模块化提供有效途径和工具;
(7)算法结构清晰,层次分明,便于算法正确性的证明和复杂性的分析。
描述算法
Java
程序结构
数据类型
方法
异常
Java的类
通用方法
垃圾收集
递归
算法设计的步骤
算法设计基本步骤
1.问题陈述
2.模型拟制
3.算法设计
4.算法正确性证明
5.算法实现
6.算法复杂性分析
7.实验测试
8.文件编制
算法复杂性分析
分析理由
要算法成功地处理一个特定输入,需要对算法所需的内存空间和运行时间进行估算或限界
能定量标准比较统一问题不同算法的效率
复杂度分类
多项式时间复杂度算法
指数时间复杂度算法
实验测试和分析
理由
试验验证算法的正确性
确定算法的实验品质
确定算法的计算限度
选择问题:测试什么,测试目的
估计算法的平均渐进运行时间
对于给定的输入,比较同类算法的性能
实验确定算法中的参数
对近似算法,测试结果接近最优值的程度
确定度量指标
实际运行时间
干扰因素
计算机上其他运行程序
高速缓存影响
内存利用率
生成测试数据
数量足够
不同规模
不同分布
编程和运行
编程
保证编程水平一致性
运行
保证干净的计算环境,减少数据噪声
数据分析
比率测试
幂测试
文件编制
问题描述和分析
建模和求解
算法设计和正确性证明过程
算法复杂度分析
测试结果记录和分析报告
输入/输出要求及格式描述
用T(N,I)表示算法A在一台抽象计算机上的时间复杂度
N:待求解问题的规模
DN:所有可能的输入规模为N的输入构成的集合
P(DN):DN的概率分布
I:算法的输入,I∈DN
时间复杂度度量
符号说明
O
定义
数学形式定义
O(g(n))是以g(n)为上界的所有函数
符号理解
运算规则
对于(1)的证明
Ω
θ
o