数据结构基础概念,时间复杂度、空间复杂度基础概念
数据结构基础概念(C语言)
程序=算法+数据结构
数据结构
数据结构(data structure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
这里只进行对基础概念和知识点的表述
-
定义
数据(Data):所有能输入到计算机中并被计算机处理的符号的总称。
数据元素(Data Element):数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
数据项(Data Item):组成数据元素的、有有独立含义的、不可分割的最小单位。
数据对象(Data Object):性质相同的数据元素的集合,是数据的一个子集。
此图更直观的描述它们之间的关系:
-
研究对象
数据的逻辑结构
数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。它可看作是从具体问题抽象出来的数学模型。逻辑结构包括:
1.集合结构:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;
2.线性结构:数据结构中的元素存在一对一的相互关系;
3.树结构:数据结构中的元素存在一对多的相互关系;
4.图形结构:数据结构中的元素存在多对多的相互关系。数据存储结构
数据对象在计算机中的存储表示称为数据的存储结构,也称物理结构。数据元素在计算机中有两种基本的存储结构,分别是:
1.顺序存储结构:将数据放在地址连续的存储单元里
2.链式存储结构:将数据存储在任意的存储单元里,通过保存地址的方式找到相关联的数据元素
算法
指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。
数据结构只是静态地描述了数据元素之间的关系,而一个高效的程序则需要在数据结构的基础上设计和选择算法。
算法是独立存在的一种解决问题的方法好思想
对于算法而言,语言并不重要,重要的是思想
算法的特性:输入、输出、又穷性、确定性、可行性
评价算法优劣的基本标准:正确性、可读性、健壮性、高效性
判断一个算法的效率时,往往只需要关注操作数量的最高次项,其他次要项和常数项可以忽略
-
算法的时间复杂度
衡量算法效率的方法主要分两类:事后统计法和事前分析估计法(常用)
大O表示法 ‘O( )’
1.算法效率严重依赖于操作数量
2.在判断时首先关注操作数量的最高次项
3.操作数量的估算可以作为时间复杂度的估算常见的时间复杂度类型
关系:
在没特殊说明时,我们所分析的算法的时间复杂度都是指最坏的时间复杂度 -
算法的空间复杂度
大O表示法同样适用于空间复杂度
通过计算算法的存储空间实现:S(n) = O(f(n))
n为问题规模,f(n)为为在问题规模为n所占用存储空间的函数
对于一个算法而言,其时间复杂度和空间复杂度往往是相互而言的,但在多数情况下,鉴于运算空间比较充足,我们往往以算法的时间复杂度作为衡量算法的优劣。
**声明:此博客只是作者为了熟悉知识点而写的笔记
借鉴:《数据结构》(C语言版)(第2版)严蔚敏
__ kelly__的数据结构笔记(一)www.cnblogs.com/it-cen/p/4217166