数据结构与算法---基础篇1.1
数 据 结 构
集合:结构中的数据元素之间除了“同属于一个集合”的关系之外,别无其他关系。(不就是在某个范围内吗,有些高级语言中同一个容器里面的元素之间就是集合关系)
线性结构:1:1的关系。在线性结构中,集合中的元素,有且仅有一个开始结点和一个终端结点,除了开始结点和终端结点以外,其余结点都有且仅有一个直接前驱和直接后继
(树型和图型结构都是非线性结构)
树型结构:1:n的关系。除了根结点(起始结点)外,各节点都有唯一的直接前驱;所有的结点都可以有0个至多个直接后继
图型结构:m:n的关系。每个结点都可以有多个直接前驱和多个直接后继
存 储 结 构
顺序存储---队列、数组...
链式存储--链表..
索引存储--键值对、索引表..
散列存储--散列函数来确定数据存储地址或查找地址
算 法 效 率 估 计
(一般按最坏情况分析):
时间复杂度:简单操作次数的多少,计算频度。如果太复杂的,可以估算单条语句的大概时间然后乘上循环次数算出大概时间复杂度
T(n) = O(f(n))
当n很大时有如下关系:
O(1)
空间复杂度:程序运行从开始到结束所需要的存储空间。除了需要存储空间来存放本身所用的指令、常数、变量和输入数据外,还需要一些对数据进行的工作单元和实现算法所必须的辅助空间。在进行时间复杂度分析时,如果所占空间依赖于特定的输入,一般都按最坏的情况来分析
S(n) = O(f(n))(n为问题的规模)
领取专属 10元无门槛券
私享最新 技术干货