wordpress建购物网站,可信赖的购物网站建设,wordpress怎么绑域名,电商网站开题报告基本概念
数据是信息的载体#xff0c;是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据是计算机程序加工的原料。
数据元素是数据的基本单位。通常作为一个整体进行考虑和处理#xff0c;用一个数据元素描述一个个体。一…基本概念
数据是信息的载体是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据是计算机程序加工的原料。
数据元素是数据的基本单位。通常作为一个整体进行考虑和处理用一个数据元素描述一个个体。一个数据元素可由若干数据项组成。
数据项是构成数据元素的不可分割的最小单位。数据项如果再细分可以称这个数据项是组合项。例如时间可以拆分为年月日。
数据对象是具有相同性质的数据元素的集合是数据的一个子集。
数据对象人 数据元素具有相同性质出生日 数据项组合项年月日
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构这门课着重关注的是数据元素之间的关系和对这些数据元素的操作而不关心具体的数据项内容。
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
原子类型其值不可再分的数据类型
bool类型int类型
结构类型其值可以再分解为若干成分(分量)的数据类型。
结构体
抽象数据类型(Abstract Data Type, ADT)是抽象数据组织及与之相关的操作。
定义一个ADT 就是在“定义”一种数据结构确定了ADT的存储结构才能实现这种数据结构。
数据结构三要素 逻辑结构 集合结构 线性结构一对一 树形结构一对多 图形结构多对多 数据运算 物理结构存储结构 顺序存储物理上相邻非顺序离散存储物理上不相邻 链式存储索引存储散列存储
若采用顺序存储则各个数据元素在物理上必须是连续的若采用非顺序存储,则各个数据元素在物理上可以是离散的。
数据的存储结构会影响存储空间分配的方便程度。
数据的存储结构会影响对数据运算的速度。Eg在b和d之间插入新元素c
算法
程序 数据结构 算法
数据结构要处理的信息。
算法处理信息的步骤。
算法(Algorithm)是对特定问题求解步骤的一种描述它是指令的有限序列其中的每条指令表示一个或多个操作。
算法必须具备的5特性
有穷性一个算法必须总在执行有穷步之后结束且每一步都可在有穷时间内完成。注算法必须是有穷的而程序可以是无穷的。确定性算法中每条指令必须有确切的含义对于相同的输入只能得出相同的输出。可行性算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。输入一个算法有零个或多个输入随意有无数量这些输入取自于某个特定的对象的集合。输出一个算法有一个或多个输出必须有这些输出是与输入有着某种特定关系的量。
好算法的特性
正确性算法应能够正确地解决求解问题。可读性算法应具有良好的可读性以帮助人们理解。健壮性输入非法数据时算法能适当地做出反应或进行处理而不会产生莫名其妙的输出结果。高效率时间复杂度低花费时间少。低存储量需求空间复杂度低不费内存。
算法效率的度量
先让算法运行事后统计时间因为在不同的机器上运行的时间不同所以不具有参考这样不可以。还存在什么问题
和机器性能有关如超级计算机 v.s.单片机和编程语言有关越高级的语言执行效率越低和编译程序产生的机器指令质量有关有些算法是不能事后再统计的如导弹控制算法
时间复杂度
时间开销与问题规模 n 之间的关系
事前预估算法时间开销T(n)与问题规模 n 的关系(T表示“time” )
加法规则多项相加只保留最高阶的项且系数变为1 T ( n ) T 1 ( n ) T 2 ( n ) O ( f ( n ) ) O ( g ( n ) ) O ( m a x ( f ( n ) , g ( n ) ) ) \begin{equation}\begin{split} T(n) T_1(n) T_2(n) \\ O(f(n)) O(g(n)) \\ O( max( f(n), g(n) )) \end{split}\end{equation} T(n)T1(n)T2(n)O(f(n))O(g(n))O(max(f(n),g(n)))
乘法规则多项相乘都保留 T ( n ) T 1 ( n ) × T 2 ( n ) O ( f ( n ) ) × O ( g ( n ) ) \begin{equation}\begin{split} T(n) T_1(n) × T_2(n) \\ O(f(n)) × O(g(n)) \\ \end{split}\end{equation} T(n)T1(n)×T2(n)O(f(n))×O(g(n))
Eg: T 3 ( n ) n 3 n 2 l o g 2 n O ( n 3 ) O ( n 2 l o g 2 n ) O ( n 3 ) \begin{equation}\begin{split} T_3(n) n^3 n^2 log_2n \\ O(n^3) O(n^2 log_2n) \\ O(n^3) \end{split}\end{equation} T3(n)n3n2log2nO(n3)O(n2log2n)O(n3) 结论
结论1顺序执行的代码只会影响常数项可以忽略。结论2只需挑循环中的一个基本操作分析它的执行次数与n 的关系即可。结论3如果有多层嵌套循环只需关注最深层循环循环了几次。
三种复杂度
最坏时间复杂度最坏情况下算法的时间复杂度。平均时间复杂度所有输入示例等概率出现的情况下算法的期望运行时间。最好时间复杂度最好情况下算法的时间复杂度。
复杂度排行
常数对数线性线性对数平方立方指数阶乘幂指时间复杂度 O ( 1 ) O ( l o g 2 n ) O ( n ) O ( n l o g 2 n ) O ( n 2 ) O ( n 3 ) O ( 2 n ) O ( n ! ) O ( n n ) O(1) O(log_2n) O(n) O(nlog_2n) O(n^2) O(n^3)O(2^n) O(n!) O(n^n) O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)O(nn)
空间复杂度
空间开销(内存开销)与问题规模 n 之间的关系
无论问题规模怎么变算法运行所需的内存空间都是固定的常量算法空间复杂度为 S(n) O(1)
注S表示“Space”。
算法原地工作——算法所需内存空间为常量。
变量定义会增加内存开销
e.g.int a;一个int4B那么就有S(n) O(4) O(1)
int a[n]; 那么就有S(n) O(4n) O(n)
int a[n][n]; 那么就有S(n) O(n^2)
函数递归调用带来的内存开销
空间复杂度 递归调用深度
