【数据结构精讲】01绪论（基本概念介绍和时间复杂度计算）
绪论
在绪论这部分会介绍常用的一些基本概念，让同学们对这门课的整体有所了解！
数据结构以及相关概念
一、几个重要概念
1、数据：凡是能输入到计算机并能被计算机程序处理的符号的总称
2、数据元素：数据的基本单位（数据项为最小单位）又可称为记录、结点或顶点，通常作为整体进行处理。
3、数据对象：具有相同性质的数据集合，例如：整数集合，质数集合。
4、数据结构：彼此之间存在一种或者多种特定关系的数据元素的集合。
二、数据结构的基本类型
1、集合（彼此孤立）
2、线性结构（一对于一关系）
3、树形结构（一对多关系）
4、图形结构（网状结构）
三、数据结构的组成
研究范围——三个方面（逻辑结构、物理结构、运算）
1、逻辑结构（不依赖计算机）
定义：描述数据元素与数据元素之间的某种固有的逻辑关系。通常表示为：B=（D，R）
D:数据元素的有限集 R:关系的有限集
2、物理结构（依赖计算机）
定义：数据的逻辑结构在计算机存储器上的实现
目标：①存储元素②体现元素与元素之间的关系
四种储存方法：
（1）顺序存储法：把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元中。（可以用数组实现）
如：已知Loc(a1)
则Loc（a2）=Loc(a1)+L
Loc(ai)=Loc(a1)+(i-1)L(这样我们就可以随机的访问我们的数组中第i个元素所在的位置)
（2）链式存储法：将储存结点的存储单元一分为二，一部分储存自身的数据信息（数据域），另一部分存储后续结点的地址（指针域）
例：（a1,a2,a3,…，an）对删除、插入方便，查找就比较复杂
（3)索引储存法：利用结点的索引号来确定地址的方法。
（4）哈希法（散列法）：利用结点的值来确定结点地址的方法，其关键是找一个寻求恰当的哈希函数H(key)。
例如：H(key)=key mod 5 key:17,60,29,20,25
用哈希法存储如下：
3、运算
在数据的逻辑结构上定义的操作算法。例如：建立、查找、插入、删除、排序、遍历等。
四、算法及其评价
1、算法的含义：解决某一特定类型问题的有限运算序列，其实就是解决问题的方法与思路。
2、算法的五大特征
有穷性、确定性 、可行性、输入（可以有0个或多个），输出（1个或者多个）。
3、评价算法的四个标准
正确性、可读性、健壮性、时间复杂度、空间复杂度。
五、时间复杂度的计算
1、时间复杂度的含义
（1）频率：算法中基本语句重复执行的次数，通常用f(n)表示。
（2）时间复杂度：算法中基本语句重复执行的次数的数量集。T(n)=O(f(n))
（3）常用的有：O（1）常量阶，O（n）线性阶,O(log2n)对数阶,O(nlog2n)线性对数阶,O(n2)平方阶等
六、例题
PS:下面的代码块是通过伪代码的形式展示，大家只需要有点C语言基础，看得懂代码的执行流程即可！
（1）
{
int i;
for(i=1;i<=n;i*=2)
x++;
}
解：计算时我们先计算频度f(n)，再计算时间复杂度T（n）。
出现 i*=2 的形式一般都是log2n对数阶的形式
f(n)=O(log2n) T(n)=O(log2n)
（2）
{
int i,j;
for(i=1;i<=n;i*=2)
for(j=1;j<=n;j++)
x++;
}
解：对于这道题，有双层循环，我们先假设最外层循环，会执行k次，而最内层循环显而易见外层执行1次，内层执行n次。我们用f(xi)表示当外层循环下标为i时，对应x的执行次数！
则梳理程序流程，当i=1,f(x1)=n;当i=2,f(x2)=n;i=4,f(x4)=n,…,i=k,f(xk)=n
我们做一个数据的累加f(n)=n+n+n+…+n=kn(x每次循环执行n次，一共执行k次，则最终的频率为kn)
我们已经得到f(n)=k*n，现在需要解决的是将k通过n的形式表达出来，再带入f(n)表达式中，就可以得到f(n)完整表达式。
如何求k?
k表示最外层循环的次数，即满足i<=n的i最大值，而i是通过i*=2的形式出现，在（1）中我们也提到i *= 2的形式,i的最大值为log2n,即k=log2n
则f(n)=k*n=nlog2n ,T(n)=O(nlog2n)
总结
通过上面两个关于时间复杂度的计算，我们知道，对于一些比较复杂的程序要分析其时间复杂度的时候
，要先分析程序的执行流程，然后计算其频率，最后再计算时间复杂度！