一站式网站开发服务平台,网站推广由什么样的人来做,珠海百度推广优化排名,ios编程语言是什么#xff08;一#xff09;数据结构的基本概念
1.相关名词 【1】数据
1.信息的载体#xff0c;描述客观事物
2.能被输入到计算机中
3.能被计算机程序识别和处理的符号的集合。
【2】数据元素
1.数据的一个“个体”
2.数据的基本单位
3.有时候也被称为元素、结点、顶点…一数据结构的基本概念
1.相关名词 【1】数据
1.信息的载体描述客观事物
2.能被输入到计算机中
3.能被计算机程序识别和处理的符号的集合。
【2】数据元素
1.数据的一个“个体”
2.数据的基本单位
3.有时候也被称为元素、结点、顶点、记录等这时候用于完整描述一个对象。ex一条学生记录
【3】数据项
1.组成数据元素具有特定意义不可分割的最小单位
2.数据元素是数据项的集合
3.比如说在学生信息表中的一条学生记录数据元素中这个学生的学号或者性别这些都是数据项
【4】数据对象
1.具有相同性质的数据元素的集合
2.是数据的一个子集
【5】数据结构通过抽象方法研究一组具有特定关系的数据的存储和处理主要研究三个方面三要素逻辑结构、存储结构和数据运算。
2.数据结构的三要素逻辑结构存储结构数据运算
【1】逻辑结构 有2种划分方式:1.按照线性和非线性分 2.按照结构分
1.线性和非线性
1线性线性表、栈和队列、字符串、数组和广义表
2非线性树和图
2.结构分4种
1集合结构在同一个集合中它们之间无关系
2线性结构任意一个元素之间有且仅有一个前驱和后继1对1
3树形结构有一个前驱多个后继1对多
4图形结构有多个前驱多个后继多对多
【2】存储结构存储的逻辑结构4种顺序、链式、索引、散列哈希
*索引类似课本目录每页都有页码i检索时利用结点页的顺序号i确定位置
*散列也称哈希存储用哈希函数将数据元素按照关键字和唯一的存储位置关联
【3】数据运算插入、删除、查找、修改、排序等
二算法和算法分析
1.算法的基本概念
1.指令的有限序列
2.可以用自然语言描述
3.算法具有5个重要特性有穷、确定、可行、输入输出
*有穷步骤和执行时间有限
*确定有确切含义、无二义、只有唯一的一条执行路径对于相同的输入有唯一的执行结果
*可行执行有限次实现
*输入0或多个
*输出1或多个最少1个结果
4.算法和程序是两个不同的概念区别
*执行时间算法步骤有限有穷性程序无限次执行
*语言描述程序必须用规定语言算法无限制可自然语言。
5.算法的基本目标正确、易读、健壮、高效率
*健壮当环境发生变化非法输入时候可以适当做出反应或者处理不会产生不正确的结果
*高效率较高的时间用时少和空间性能占用空间少
6.算法的评价方法事前分析、事后统计
2.算法的时间和空间性能分析
【1】时间复杂度
1.TN表示该算法时间耗费N为求解问题的规模
2.当N趋向于无穷时候仅考虑数量级阶就是算法的渐进时间复杂度用大o表示法
3.大o表示法就是忽略系数类似数学的“抓大头”
4.语句频度重复执行的次数
【2】用大o表示法求解算法的渐进时间复杂度有6类
1. 常量阶 O(1)算法的执行时间不随输入数据的规模n变化即无论输入数据有多大算法的执行时间都是固定的。这类算法通常只包含基本操作如赋值、比较等。
2. 对数阶 Olog n)算法的执行时间随输入数据的规模n的对数增长。这类算法通常涉及到二分搜索或树结构的深度遍历。
3. 线性阶 O(n)算法的执行时间随输入数据的规模n线性增长。这类算法通常涉及到对数据的顺序访问如数组或列表的遍历。
4. 平方阶 O(n^2)算法的执行时间随输入数据的规模n的平方增长。这类算法通常涉及到两层嵌套循环如矩阵的乘法或对数组的每个元素进行比较。
5. 线性对数阶 O(n log n)算法的执行时间是输入数据的规模n与对数的乘积。这类算法通常涉及到排序操作如快速排序或归并排序。
6. 立方阶 O(n^3)算法的执行时间随输入数据的规模n的立方增长。这类算法通常涉及到三层嵌套循环如矩阵乘法的直接实现。
