数据结构概论和时间复杂度的简单求法

1 基本概念和术语

 

• 数据（Data）——对客观事物的符号表示，在计算机科学中指能输入到计算机中并被计算机程序处理的符号的总成。数据的含义极广，如图像、声音等都可以通过编码而归之于数据的范畴。

• 数据元素（Data Element）——数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

• 数据项（Data Item）——数据项是数据的不可分割的最小单位。

• 数据对象（Data Object）——性质相同的数据元素的集合，是数据的一个子集。

• 数据结构（Data Structure）——相互之间存在的一种或多种特定关系的数据元素的集合。

• 物理结构（存储结构）——数据结构在计算机中的表示，包括数据元素的表示和关系的表示。计算机中表示信息的最小单位是位（bit），可以使用多个位形成的位串表示一个数据元素，通常称这个位串为元素（element）或结点（node）。

• 数据类型（Data Type）——刻画操作对象的特性，是一个值的集合和定义在这个值集上的一组操作的总称。

2 四种数据结构

• 集合

• 线性结构——结构中的数据元素之间存在一对一的关系

• 树形结构——结构中的元素存在一对多的关系

• 图（网）状结构——结构中的数据元素之间存在多对多的关系

3 数据结构的形式定义

Data_Structure = (D,S)

D——数据元素的有限集
S——D上关系的有限集

4 算法及评价

算法是解决某一特定类型问题的有限运算序列。

算法的时间复杂度是衡量一个算法好坏的重要指标。

时间复杂度是指算法中所包含简单操作执行次数的数量级。

语句的频度是需要精确计算算法中某一语句执行的次数。

 

算法花费的时间与算法中语句的执行次数成正比，一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)，也叫做问题规模。一般情况下，算法中基操作重复执行的次数是问题规模n的某个函数，用T(n)表示。

按数量级递增排列，常见的时间复杂度有：

常数阶O(1)

对数阶O(log2n)

线性阶O(n)

线性对数阶O(nlog2n)

平方阶O(N^2)

立方阶O(N^3)

 

例1：

 

for(i=0;i<n;i++){
    y=y+1;
    for(j=0;j<2*n;j++){
        x++;
    }
}

例1中的时间复杂度计算方法：

首先找最里层的循环，发现x++这段代码应该是循环次数最多的语句，根据两层循环的循环量计算x++语句的频度：

n * 2n = 2n^2 = O(n^2)

则该例子的时间复杂度为：O(n^2)

例2

 

int fn(int n){
    if(n<=1){
        return 1;
    }
    return n*fn(n-1);
}

例2中不存在循环标识for,while等，但是却是递归函数，本身就具备循环含义，这样一来，就需要把递归函数转化为循环函数之后再用循环标识来计算时间复杂度。

一般计算项为：

fn(n) = fn(n-1)*n;

可转化为：

 

int fn(n){
    int i,s;
    for(i=1;i<=n;i++){
        s = s*i;
    }
    return s;
}

这样一来，就可以轻松得到时间复杂度为:O(n)

例3：

 

i=1;
while(i<=n){
    i=i*2;
}

循环语句为i=i*2，一层循环，执行频度计算方法为：2^t<=n ->  t = log2n

则该例子的时间复杂度为：log2n

 

例4：

for(int i=0;i<m;i++){
    for(int j=0;j<n;j++)
        a[i][j] = i*j;
}

此例子中，共两层循环，最里层语句为a[i][j] = i * j，执行频度为 m * n次，但是它的时间复杂度应改为O(n^2)，因为这两个n是不一样的含义的，m*n中的n是此处实实在在执行次数的n，而O(n^2)表示的是问题规模的n，也就是说m * n中的m和n都演化为问题规模的n，从而得到O(n^2)这个结果。

 

计算时间复杂度的一般方法：

（1）找循环标识for,while的关键字

（2）如果是递归函数，先将递归函数化为循环函数

（3）找出每一层循环的循环量

（4）计算最里层循环语句的频度

（5）取数量级最大的最为时间复杂度