u=2054310334,785908068&fm=26&gp=0.jpg
时间复杂度
1.一个算法是由控制结构（顺序、分支、循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。
一般情况下算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作 T(n) = O(f(n)),它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。
例如 for(i=1;i < n; I++),该算法的时间复杂度是 O(n).
线性表
简单的说一个线性表是n个数据元素的有限序列。
稍微复杂的线性表中，一个数据元素可以有若干个数据项组成，在这种情况下，常把数据元素成为记录，含有大量记录的线性表又称为文件。注意:线性表中的数据元素可以是各种各样的，但是同一线性表中元素必定具有相同特性。
线性表的特点：
在数据元素的非空有限集中，（1）存在唯一的一个被称为‘第一个’的数据元素；（2）存在唯一的一个被称为‘最后一个’的数据元素；（3）除了第一个以外，集合中的每个元素都只有一个前驱；（4）除了最后一个数据元素以外，集合中每个数据元素均只有一个后继。
线性表的存储分为顺序存储和链式存储
1.线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表中的数据元素。换句话说，以元素在计算机内“物理位置相邻”来表示线性表内元素之间的逻辑关系。
LOC(ai) = LOC(a1) + (n - 1)*l;
由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储是一种随机存取的存储结构。
插入和删除元素是有大量的数据元素移动，时间复杂度为O(n)
链式存储
结点：包含指针域和数据域
链表的存取必须从头指针开始进行，头指针指示链表中第一结点的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为空（NULL）
有时，我们在单链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储线性表的长度类的附加信息，头结点的指针域存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空。
单链表的数据查找必须从头指针出发寻找，因此，单链表是非顺序存取的存储结构。
链表的插入和删除时，时间复杂度也是O(n),因为需要从头结点开始遍历找到需要删除或者插入的位置.但是由于链表在空间的合理利用上和插入、删除时不需要移动等优点，因此在很多场合下，它是线性表的首选存储结构。然而，它也存在着实现某些基本操作，如求线性表的长度时不如顺序存储结构的缺点。
网友评论