时针的个人网站

Appearance

什么是数据结构 ​

数据结构 ​

问题引入：假如你是一位图书管理员，给你一堆书架和书本，现在让你分类和管理它们。

于是你就要考虑四个问题：新书怎么插入，旧书怎么删除，书架怎么替换，书本怎么查找

也就是我们常说的增删改查。

我们先来看几个方案：

1.随便放 新书插入很简单，直接放上去就可以了，但是查找起来很困难。

2.按字母顺序放 查找时可以用二分查找法。但是插入新书就比较麻烦了。

3.按分类放(实际操作) 每块指定要放什么类别的书本，每个类别里再按照字母顺序放。

  • 插入：先定类别，二分查找确定位置，移出空位。
  • 查找：先定类别，再二分查找。

数据结构就是这样，它是用来组织、存储和处理数据的一种方法。

算法 ​

先来看一个简单的例子：写一个函数printN,使得传入一个正整数n，打印1到n的整数。 方法一，循环：

c
void printN(int n){
    int i  = 1;
    for (i = 1; i <= n; i++) {
        printf("%d \n", i);
    }
}

方法二，递归：

c
void printN(int n){
    if (n == 0) {
        return;
    }
    printf("%d \n", n);
    printN(n-1);
}

发现循环能跑到10万，递归跑不到。 因为递归需要保存调用栈，而栈的大小受限于系统的内存，所以递归很容易导致栈溢出。 于是定义空间复杂度，来衡量算法需要的内存空间。

再来看一个例子： 写程序计算给定多项式在给定点x处的值。

f(x)=anxn+an−1xn−1+...+a1x+a0

方法一，直接用pow函数计算：

c
double calculate(int n , double a[],double x){
    int i;
    double p = a[0];
    for(i=1,i<=n,i++){
        p+=a[i]*pow(x,i);
    }
    return p;
}

看起来很不错，对吧？几乎所有编程语言都会给我们pow函数，但是如果你这么写，会招来老登的批评以及南梁的嘲笑——时间复杂度太高了。

方法二，秦九韶算法(秦九韶太超模了)： 其实就是提公因式，把次方运算变成一次加法和一次乘法，你可以自己看看这个式子，和上面的式子是等价的。

f(x)=a0+x(a1+x(...(an−1+x(an))))
c
double calculate(int n , double a[],double x){
    int i;
    double p = a[n]; //这个时候就要倒过来循环，因为计算步骤是从后往前的
    for(i = n;i>0;i--){
        p = a[i-1]+x*p;
    }
    return p;
}

你可以让AI帮你打clock,会发现运算速度差了一个数量级。

于是为了衡量算法的效率，我们定义时间复杂度。计算机乘除一般比加减开销大，所以我们用乘除次数比较上面两个算法的时间复杂度。

方法一： 从左往右，一次计算0,1,2,3 ... n+1次乘法，加起来0+1+2+...+n+1=n(n+1)/2=n2+n2次乘法。当n很大时，可以把二次项后面的数量级忽略，再忽略系数，所以时间复杂度为O(n2)。

方法二： 显然每次循环都只是一次乘法一次加法，算法的时间复杂度必然是线性的，也就是O(n)。

所以，秦九韶算法的效率要比pow函数高很多。

数据结构与算法的任务 ​

数据结构： 就是数据对象在计算机中的存储和组织方式。

  • 逻辑结构
  • 物理存储结构

抽象数据类型(ADT): 就是对数据结构的一种抽象，它定义了数据结构的操作和功能。

  • 数据对象集
  • 数据集合相关联的操作集

例如：

  • 类型名称：矩阵(Matrix)
  • 数据对象集：一个M行N列的矩阵Am×n=((aij)1≤i≤m,1≤j≤n). 由M×N个元素组成。其中a是矩阵元素的值，ij是矩阵元素所在的行号和列号。
  • 操作集：矩阵的加法、减法、乘法、求逆、求秩、求行列式、求特征值、求解线性方程组.....等函数

复杂度分为最坏情况复杂度、平均情况复杂度

最大子列问题这个自己听课吧，总之面对O(n2)的算法时，想一想有没有O(nlogn)的算法。