SCS_user_EHQ0z2l6el查看:3 回复:3 评论:3 创建时间:2023-04-25T21:46:16用户:SCS_user_EHQ0z2l6el查看:3 回复:3 评论:3 创建时间:2023-04-25T21:46:16
这篇我们来讲点基础的
数据的结构与算法概念、算法的时间、空间复杂度
数据的结构
数据
数据分为两种类型
一种是数值性数据(numetric data)
是按数字尺度测量的观察值,其结果表现为具体的数值。
现实中所处理的大多数都是数值性数据。
比如我身高1145cm就是数据性数据
一种是非数值性数据(non-numeric data)
以事物现象的属性或类别为主要特征。
比如我是男的就是非数值型数据
结构
结构具有空间位置关系和相互作用和依赖关系
（我忘了啥意思了，感兴趣的可以去百度一下）
四种基本结构
1.集合结构
例如map
2.线性结构
例如栈、队列、链表
线性结构一般都很“整齐”
3.树形结构
例如二叉树
树形结构是有父子节点之分的
4.图形结构
例如图
和树形结构不同的是，图形结构的每个顶点都是平等的
这里考大家一个问题
下面哪一个是线性结构（____）
A.stack B.binary tree C.grath D.Your Mother
算法概念
算法
算法是对特定问题求解步骤的一种描述，
就好比你写数学题（可以是物理题，这里可以随便讨论）的过程一样
是一有限长的操作序列
算法特性
有穷性:算法在执行有穷步骤后能结束
希望你不要在while（true）里不写break
确定性:每步定义都是确切的、无歧义的
可行性:每一条运算应足够基本
输入:有0个或多个输入
输出:有1个或多个输出
这里要说明的是，算法是算法
你写的连点器代码不需要输出，但是它不是算法
算法设计的要求
正确性:满足具体问题的需求（废话）
可读性:便于理解和修改（注释）
健壮性:输入数据非法时，也能适当反应（终止条件或者函数开始的时候判断）
效率高:执行时间少（废话）
空间省:执行中需要的最大存储空间（废话）
算法复杂度
时间复杂度
衡量算法的效率，主要依据算法执行所需要的时间，即时间复杂度
事后统计法:计算算法开始时间与完成时间差值
事前统计法:依据算法选用何种策略及问题的规模n，一般用这种
时问复杂度是问题规模n的函数f(n)，即：
O(f(n))：O表示趋向于括号里面特定的参数，即≤f(n)
一般地，时间复杂度用算法最深层循环内的语句中的原操作的重复执行次数表示。
比较绕
我举个例子
y += 1;时间复杂度是O（1）常量级
for（int i=0；i<n;i++)sum+=114514;时间复杂度是O（n）线性级
for（int i=0；i<n;i++)or（int j=0；j<n;j++)sum+=1;时间复杂度是O(n的平方）平方级
for(i=1; i<n; i*=2) sum += 1;时间复杂度是O（log2n）对数级
除了上述例子提到的，常用的还有排列阶O(n!)，指数阶O(2的n次方)
如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度
如果无法求取平均时间复杂度，则采用最坏情况下的时间复杂度
时间复杂度是衡量算法好坏的一个最重要的标准
空间复杂度
空间复杂度指算法执行时，所需要存储空间的度量，它也是问题规模的函数即
S（n）=O（f（n））
开辟一个变量的空间复杂度是S（1）
一个数组是S（n）
好了，有关数据的结构与算法概念、算法复杂度的内容我就介绍到这里了
感兴趣的朋友可以去翻我之前的教学链接
再见awa
