黑龙江建设人力资源网站,wordpress 整站,下载手机app软件,wordpress顶部代码1.1 计算机问题求解
一般而言#xff0c;人们需要的不是解决一个具体问题的程序#xff0c;而是解决一类问题的程序。
对于求平方根这样的简单问题#xff0c;人们希望的也不是专用于求某个数(例如2)的平方根的函数#xff0c;而是能求任何数的平方根的函数。
用计算机解…1.1 计算机问题求解
一般而言人们需要的不是解决一个具体问题的程序而是解决一类问题的程序。
对于求平方根这样的简单问题人们希望的也不是专用于求某个数(例如2)的平方根的函数而是能求任何数的平方根的函数。
用计算机解决问题的过程分为两个阶段: 1、程序开发者针对要解决的问题开发出相应的程序 ---- 程序设计 2、使用者运行程序处理问题的具体实例完成具体计算。 ---- 功能使用
1.1.1 程序开发过程
1、需求分析阶段---模糊需求细化
2、设计阶段---严格描述求解过程
3、编码阶段 -- 使用编程语言写代码实现
4、检查测试阶段 --- 检查语法错误修正逻辑错误 1.3、算法和算法分析
1.3.1、问题、问题实例和算法
算法性质有穷性、可行性、确定性、终止性、输入/输出。
算法描述问题解决的办法要方便人们的阅读和使用。常见的算法枚举法、贪心法、分治法、回溯法、动态规划、分值限界法等。
程序算法的实现算法的落地。
算法设计模式是人们对经验的总结只能借鉴不应作为教条。这些模式并不相互隔绝也不互相排斥。例如一般而言复杂的问题都需要分解;而最简单的情况经常可能采用枚举和判断的方式处理。
1.3.2、算法的代价及其度量
在研究现实世界中的计算问题时必须考虑计算的代价。该算法:在求解过程中需要多少存储空间?完成问题实例的求解需要多长时间?
同一个算法能应用于不同的实例计算的实际代价通常与实例的规模(大小)有关。3000X3000的矩阵计算自然要比3X3的矩阵计算花费更多的时间和空间。因此可以把一个算法的计算(时间和空间)开销定义为问题的实例规模的函数。
算法分析就是针对一个具体算法设法确定一种函数关系以问题实例的某种规模n为参量反映出这个算法在处理规模n的问题实例时需要付出的时间(或者空间)代价。
同一算法在大规模集合操作中比如在一个数组中查找某一个数据可能很快就找到了可能要耗费很长时间才能找到。因此在有关算法的研究和分析中人们主要关注算法的最坏情况代价有时也关注算法的平均代价。
“大O记法描述算法性质 时间复杂度T(n)O(g(n)) 空间复杂度S(n)O(g(n)) 常用的复杂度函数 O(1) ---- 常量复杂度 O(log n) --- 对数复杂度 O(n) ----- 线性复杂度 O(nlog n) O(n^2) --- 平方复杂度 O(n^3) ---- 立方复杂度 O(2^n) ---- 指数复杂度 1.3.3、算法分析
0.基本操作认为其时间复杂度为O(1)。如果是函数调用应该将其时间复杂度代入参与整体时间复杂度的计算。 1.加法规则顺序复合)。如果算法或所考虑算法片段)是两个部分(或多个部分)的顺序复合其复杂性是这两部分(或多部分)的复杂性之和。以两个部分为例: T(n)Ti(n)T(n)O(T (n))O(T2 (n))O(max (T(n), T2 (n))) 其中T;(n)和T(n)分别为顺序复合的两个部分的时间复杂度。由于忽略了常量因子加法等价于求最大值,取T(n)和 T2(n)中复杂度较高的一个。 2.乘法规则(循环结构)。如果算法或所考虑的算法片段)是一个循环循环体将执行T(n)次每次执行需要T(n)时间那么: T(n)一T(n)×T2(n)O(T (n)×O(T(n))O(T(n)×T2(n)) 3.取最大规则(分支结构)。如果算法或所考虑算法片段)是条件分支两个分支的时间复杂性分别为T(n)和 T2(n)则有: T(n)O(max(T(n),T2(n))) 1.4、数据结构
数据结构(data structure)研究数据之间的关联和组合的形式总结其中的规律性发掘特别值得注意的有用结构研究这些结构的性质进而研究如何在计算机里实现这些有用的数据结构以支持相应组合数据的高效使用支持处理它们的高效算法。
典型数据结构集合结构、序列结构、层次结构、树形结构、图形结构
用数据结构存储信息不仅要考虑如何把抽象的数据结构映射到计算机或程序可以表达操作的数据存储形式还要考虑作用于具体数据结构的各种操作如结构的建立、其中元素的访问、插入或删除元素等一般性操作。
数据结构上的操作需要通过算法实现。
1.4.3、python对象和数据结构
Python变量的值都是对象,可以是基本整数、浮点数等类型的对象,也可以是组合类型的对象,如 list等。
Python语言中变量的这种实现方式称为变量的引用语义在变量里保存值(对象的引用。采用这种方式变量所需的存储空间大小一致因为其中只需要保存--个引用。
Python里面的内存管理系统变量在栈区值在堆区。 Python程序内部有一个存储管理系统负责管理可用内存为各种对象安排存储支持灵活有效的内存使用。
python标准的数据结构list(表)、tuple(元组)、dict(字典).
