数据结构与时间复杂度

数据结构

什么是数据结构

数据结构:是相互之间存在的一种或多种特定关系的数据元素的集合

逻辑结构与物理结构

按照视点的不同把数据结构分为逻辑结构和物理结构。

逻辑结构

数据对象中数据元素之间的相互关系

集合结构中的元素同属于同一个集合，之间没有任何关系，各个数据元素是“平等的”

线性结构中的数据元素是一对一的关系

树形结构中的数据元素存在一对多的层次关系

图形结构的数据元素是多对多的关系

物理结构

逻辑结构在计算机的存储形式

顺序存储结构
1. 数据元素存放在地址相同的存储单元
2. 数据间逻辑关系和物理关系一致
链式存储结构
1. 数据元素存放在任意的存储单元
2. 存储单元可以是连续也可以不连续

时间复杂度

时间复杂度的时间指的是用语句的执行次数，而不是实际的时间。我们知道计算机执行乘除运算是非常消耗资源的，而加减则计算很快，时间复杂度只是一个简化的描述。

O()记法
常见的阶耗费时间的关系是:

时间复杂度练习

设 n 为正整数，试确定下列各程序段中前置以记号@的语句的频度

第一题

1
2
3
4
5
6
7
8


  x=91; y=100;
    while(y>0) {
        @  if(x>100)
          { x -= 10;
             y--;
          }
          else
           x++;

第二题

1
2
3
4
5
6
7


 i=1; j=0;
    while(i+j<=n) {
         @ if(i>j)
             j++;
              else
              i++;
    }

第三题

1
2
3
4


x=n; y=0;
    while(x>=(y+1)*(y+1)) {
        @  y++;
    }

第四题

1
2
3
4
5


 k=0;
    for(i=1; i<=n; i++) {
        for(j=i; j<=n; j++)
            @  k++;
    }

第五题

1
2
3
4
5


 for(i=1; i<=n; i++) {
        for(j=1; j<=i; j++) {
            for(k=1; k<=j; k++)
                @  x += delta;
    }

答案：

$$ 1100$$
$$n$$
$$\sqrt{n}$$
$$\frac{n(n+1)}{2}$$
$$\frac{n(n+1)(n+2)}{6}$$