Question

基于数据结构和算法的深入应用--1.概论

Answer 1

数据结构是计算机存储,组织数据的方式.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合.通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率.

从关注的维度看,数据结构可以划分为数据的逻辑结构和物理结构,同一逻辑结构可以对应不同的存储结构.
逻辑结构反应的是数据元素之间的逻辑关系,逻辑关系是指数据元素之间以什么形式互相关联,这与他们在计算机中的存储位置无关.逻辑结构包括:

数据物理结构指的是逻辑结构在计算机存储空间中的存放形式(也称为存储结构).一般来说,一种数据结构的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序存储,链式存储,索引存储和哈希存储等.

算法指的是基于存储结构下,对数据如何有效的操作,采用什么方式可以更有效的处理数据,提高数据运行效率.数据的运算是定义在数据的逻辑结构上,但运算的具体实现要在存储结构上进行.一般设计的操作有以下几种

简单理解,为了某种运算而花费的时间,使用大写O表示.一般来说,时间是一个不太容易计量的维度,而为了计算时间复杂度,通常会估计算法的操作单元数量,而假定每个单元运行的时间都是相同的.因此,总运行时间和算法的操作单元数量一般来讲成正比,最多相差一个常亮系数.一般来讲,常见的时间复杂度有以下几种:
1.常数阶 :时间与数据规模无关,如交换两个变量值

2.线性阶 :时间和数据规模呈线性,可以理解为n的1次方,如单循环里的操作

3.k次方阶 :执行次数是数量的k次方,如多重循环,以下为2次方阶实例

4.指数阶 :随着n的上升,运算次数呈指数增长

5.对数阶 :执行次数呈对数缩减,如下

6.线性对数阶 :在对数阶的基础上,进行线性n倍乘积

与时间复杂度类似,空间复杂度是对一个算法在运行过程中占用内存空间大小的度量.一个程序执行时除了需要存储空间和存储本身所使用的指令 常数 变量和输入数据外,还需要一些对数据进行操作的辅助空间.而空间复杂度主要指的是这部分空间的量级

同样,空间复杂度也用大写O表示,相比时间复杂度场景相对简单,常见级别为 和

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的.时间复杂度低可能借助占用大的存储空间来弥补,反之,某个算法所占据的空间小,那可能就需要占用更多的运算时间.两者往往需要达到一种权衡
在特定环境下的业务,还需要综合考虑算法的各项性能,如使用频率 数据量的大小 所用的开发语言 运行的机器系统等.两者兼顾权衡利弊才能设计出最适合当前场景的算法

把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子分体分成更小的子问题,直到最后子问题小到可以简单的直接求解,原问题的解即子问题的解的合并.这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅里叶变换,大数据的MR
分治法对问题有一定的要求:

基本思想与分治法蕾西,也是将待求解的问题分解为若干个子问题,按照顺序求解子问题,前一子问题的解,为后一个子问题的求解提供了有用的信息.在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能打到最优的局部解,丢弃其他.依次解决各子问题,最后一个子问题就是初始问题的解
与分治法最大的不同在于,分治法的思想是并发,动态规划的思想是分布.该方法经分解后得到的子问题往往不是互相独立的,其下一个子问题的求解往往是建立在上一个子问题的解的基础上.动态规划算法同样有一定的适用性场景要求:

同样对问题要求做出拆解,但是每一步,以当前局部为目标,求得该局部的最优解.那么最终问题解决时,得到完整的最优解.也就是说,在对问题求解时,总是做出在当前看来是最好的选择,而不是从整体最优上加以考虑.从这一角度讲,该算法具有一定的场景局限性

回溯算法实际上是一个类似枚举的搜索尝试过程.在每一步的问题下,列举可能的解决方式.选择某个方案往深度探究,寻找问题的解,当发现已经不满足求解条件,或深度达到一定数量时,就返回,尝试别的路径.回溯法一般适用于比较复杂的,规模较大的问题.有"通用解题法"之称

与回溯法类似,也是一种在空间上枚举寻找最优解的方式.但是回溯法策略为深度优先.分支法为广度优先.分支法一般找到所有相邻节点,先采取淘汰策略,抛弃不满足约束条件的节点,其余节点加入活节点表.然后从存活表中选择一个节点作为下一个操作对象