数据项

数据项（data item）具有原子性，是不可分割的最小数据单位。

数据元素

数据元素（data element ）是数据的基本单位，例如数据库中的一条记录

数据对象

数据对象（data object ）是性质相同的数据元素的集合，例如数据库中的一张表

数据结构分为逻辑结构，存储结构

• 逻辑结构
  • 线性结构
    • 线性表，栈，队列，数组，串
    • 除最后元素之外，其它数据元素均有唯一的"直接后继"；
    • 除第一元素之外，其它数据元素均有唯一的"直接前驱"。
  • 非线性结构
    • 树，图
    • 一对多，多对多
• 存储结构
  • 顺序存储，链式存储，索引存储，散列存储

时间复杂度

• 时间复杂度一般求的是最坏情况
• 一个简单语句的时间复杂度为O(1)。
  int count=0;
• 100个简单语句的时间复杂度也为O(1)。（100是常数，不是趋向无穷大的n）
  int count=0;
• 时间复杂度为O(log2 n)的循环语句。

int n=8, count=0;
for (int i=1; i<=n; i*=2)
    count++;

• 时间复杂度为O(nlog2n)的二重循环。

int n=8, count=0;
for (int i=1; i<=n; i*=2)
    for (int j=1; j<=n; j++)
        count++;

• 从上往下，依次增大
  常数阶O(1)
  对数阶O(log2n)
  线性阶O(n)
  线性对数阶O(n*log2n)
  平方阶O(n2)
  立方阶O(n3)

空间复杂度分析1

只看递归

int fun(int n){  
            int i，j，k，s;
         s=0;
         for (i=0;i<=n;i++)          
                              for (j=0;j<=i;j++)     
                                       for (k=0;k<=j;k++)    
                                                 s++;
         return(s);
}

由于算法中临时变量的个数与问题规模n无关，所以空间复杂度均为S(n)=O(1)。

空间复杂度分析2：

void fun(int a[]，int n，int k)
   //数组a共有n个元素
 {         int i;
            if (k==n-1)
               for (i=0;i<n;i++)　　
                      printf(“%d\n”，a[i]);  //执行n次
            else
            {  for (i=k;i<n;i++)
                        a[i]=a[i]+i*i;    　　//执行n-k次
               fun(a，n，k+1);
            }
 }

此属于递归算法，每次调用本身都要分配空间，fun(a,n,0)的空间复杂度为O(n)。

顺序表

• 特点：在内存中分配连续的空间，只存储数据，不需要存储地址信息。位置就隐含着地址。
• 优点：
  1. 节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。
  2. 索引查找效率高，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址
• 缺点：
  1. 插入和删除操作需要移动元素，效率较低。
  2. 必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费。
  3. 按照内容查询效率低，因为需要逐个比较判断

链表

• 特点：
  • 数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素每个结点是由数据域和指针域组成。
  • 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。
  • 逻辑上相邻的节点物理上不必相邻。
• 缺点：
  1. 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
  2. 查找结点时链式存储要比顺序存储慢（每个节点地址不连续、无规律，导致按照索引查询效率低下）。
• 优点：
  1. 插入、删除灵活 (不必移动节点，只要改变节点中的指针，但是需要先定位到元素上)。
  2. 有元素才会分配结点空间，不会有闲置的结点。