Question

数据结构-基本概念和时空复杂度

Answer 1

1．数据的逻辑结构与存储结构的基本概念；

数据结构的定义：数据元素之间的联系称为结构，数据结构就是具有结构的数据元素合集。

数据结构为二元组：DataStructure=(D,R)

D:Data，数据元素的有限合集，某一个数据对象

R:Relation，Data的关系合集

数据元素之间具有的逻辑关系（结构）

线性关系：如线性表，数组，堆栈，队列，串，文件等

非线性关系：树，二叉树，图，集合等

具有某种逻辑结构的数据，在计算机存储器中的存储方式(存储映像2)

特点：诸如查找，插入，删除等操作的时间效率较高，但是存储空间开销大

特点：诸如查找、删除和插入的时间效率较高，主要缺点是确定好的散列关系比较困难，即好的hash function

2．算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间复杂度和空间复杂度。

算法的定义：算法是用于解决某个特定课题的指令集合。算法就是解决问题的方法。算法是由人们组织起来准备加以实施的一系列 有限 的基本步骤。

一个完整的算法应该满足下面五个基本性质：

算法分析是指对算法质量优劣的评价。

一个程序在计算机中运行的时间多少与很多因素有关

以语句的执行次数的多少作为算法的时间量度的分析方法称为 频度统计法

整个 算法的频度 是指算法中所有的语句频度之和

关于符号 O 的定义

当且仅当存在正数 和 ,使得 对所有
成立，则称函数 与 同阶，或者说 与 同一个数量级，记作

称上式为算法的时间复杂度，或者成该算法的时间复杂度为\(O(g(n))\).

其中，n为问题的规模大小的度量。

以上算法的时间复杂度为 .

表示算法复杂度为常量，不随我呢提规模的大小而改变