数据结构学习一

发表于 更新于

学习数据结构笔记

数学基础

指数和对数

指数函数

$$f(x) = 2^x$$

其中 x = 0 那么
$$2^0 = 1$$
其中 x = 1 那么
$$2^1 = 2$$
其中 x = 2 那么，以此类推
$$2^2 = 4$$
$$2^3 = 8$$
$$2^{-1} = \frac {1} {2}$$

对应的对数是函数是指数的反函数

$$f^-1(x) = log_2^x$$

其中-1 读作 inverse，就是 f 的反函数

反推上面的指数函数得出

$$log_2^4 = 2$$
$$log_2^8 = 3$$
$$log_2^1 = 0$$

下面是以 10 为底的对数和指数

$$f(x) = 10^x$$

指数

$$f^-1(x) = log_10^x$$

以 10 为底的的对数叫做常用对数
任何数的 0 次方都是 1

$$10^0 = 1$$
$$10^1 = 10$$
$$10^2 = 100$$
$$10^3 = 1000$$
$$10^-1 = \frac {1} {10}$$

$${log_{10}}^{1000} = 3$$

那么
$${log_7}^{49} = 2$$

同理

$${log_5}^{125} = 3$$

在程序员的世界中基本上没有注明的底全都是以 2 为底，如果有其他底数会特别注明。

指数运算运算性质

主要运算性质：

  1. $$a^m*a^n = a^{m+n}$$

  2. $$\frac {a^m} {a^n} = a^{m-n}$$

  3. $$(a^m)^n = a^{mn}$$

  4. $$(ab)^n = a^n * b^n$$

  5. $$a{\frac{m}{n}} = h\sqrt a^m$$

就最后一个不太容易懂，太菜了

对数

对数式的运算性质

主要运算性质：

  1. $${log_a}^m + {log_a}^n = {log_a}^{mn}$$

  2. $${log_a}^m - {log_a}^n = {log_a}^{\frac{m}{n}}$$

  3. $${log_a}^{b^n} = n {log_a}^b $$

  4. $${log_{am}}^b = {\frac{1}{m}}{log_a}^b$$

  5. $${log_a}^b = {\frac{log_c^b}{log_c^a}}$$

  6. $$a{log_a}^b = b^c$$

这个没懂

  1. $${log_a}^a = 1$$

  2. $${log_a}^b ={\frac{1}{log_b^a}}$$

上面的都没怎么看懂，学校学的都忘了。真菜

数据结构

数据结构是计算机中储存、组织数据的方式，通常情况下，精心的数据结构可以带来最优效率的算法 – 维基百科

从上面的定义可以看到数据结构和算法是息息相关的

举例：
图书馆如何摆放图书

方法一：随便放，哪里有空放哪里随便放。
但是这样的存在的问题是，找书的时候就很乏力，书一多几乎是无法完成的任务。

方法二：按照书名拼音字母进行顺序排放
这样我们找书就可以使用二分查找法，随机抽一本书看看我们要找的书字母是在这本书之前还是之后，在确定向前还是向后然后重复这个步骤，就很快找到想要的书了，但是这种方法，弊端是插入新书，因为已经摆放好的书按顺序拜访，中间没有空位，那么插入新书就要把旧书向后挪，最坏情况是要移掉所有

那么现实中书店是如何分类的，在现实中书店是根据图书的分类进行摆放，可能分类之中还有分类

方法三：将书架划分成若干区域，每个区域按一种类别摆放图书，在每种分类中，再按照书名进行摆放。
这样查找只需要在上面的二分查找之前，先确定分类，然后二分查找，插入新书也是先找到分类然后找到位置，将书向后移，然后插入，这样，插入和查找都比较方便。

例子二：
写一个程序，实现一个函数 PrintN，使得传入一个正整数 N 的参数后，能顺序从 1 打印到 N 的所有整数。

c 语言实现

1
2
3
4
5
6
7
8
9
#include <stdio.h>

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

JavaScript 实现
JavaScript 就在 node 里面跑就好了

1
2
3
4
5
6
7
8
function main(m){
 for(let i = 1; i <= m; i++){
     console.log(i);
 }
}
main(process.argv[2])
运行的时候就是node 文件名.js 参数M的值
node在运行代码的时候可以通过process.argv来获取命令行参数，第0,1位是程序路径和主模块文件路径第三位2才是要获取的参数

第二种递归实现方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <time.h>

void PrintN(int n)
{
    if (n)
    {
        PrintN(n - 1);
    };
};

void main()
{
    clock_t start, tend;
    start = clock();
    int n = 100000;
    PrintN(n);
    tend = clock();
    printf("%lf\n", (double)(tend-start)/CLOCKS_PER_SEC);
}
在n = 100000的时候可以看到比较明显的执行过程
而执行时间大概0.02微秒

JavaScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
console.time("a")
function main(m){
 if(m == 0) return;
 main(m-1);
}
console.timeEnd('a')
main(process.argv[2])
main(process.argv[2])
10000平均执行时间在0.15毫秒
node x.js 100000 内存溢出
10000
就可以看到明显的执行过程

什么是数据结构

  1. 数据对象在计算机中组织的方式

  2. 数据对象必定与一系列加在其上的操作相关联

  3. 完成这些操作所用的方法就是算法

抽象数据类型

这句话分为
数据类型，数据类型包含：
数据对象集
数据集合相关联的操作集

抽象：
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言也无关

什么是算法

算法，算法是一个有限的指令集，可以接受或者不接受输入，但是一定有输出，一定在有限的步骤后终止，每一条指令必须有重复的目标，不可以由歧义，要在计算机能处理的范围之内，描述应该不依赖任何一种具体的语言实现的手段。

举例：
选择排序算法的伪代码描述

1
2
3
4
5
6
7
8
void SelectionSort(int List[], int N){
    // 将N个整数List[0]...List[N-1]进行非递归排序
    for(i = 0; i < N; i ++)
    MinPosition = ScanForMin(list, i, N-1);
    从List[i]到List[N-1]中找到最小元素，并将其位置复制给MinPosition.
    Swap(List[i], List[MinPostion]);
    将未排序的最小元素切换到有序部分的最后位置
}

什么是好的算法

算法的指标有一下两种：

  1. 空间复杂度 S(n) - 根据算法写成的程序在执行时占用储存单元的长度。这个长度和输入数据的规模有关，空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常终端。

  2. 时间复杂度 T(n) - 根据算法写成的程序在执行时耗费时间的长度，这个长度也和输入数据的规模有关，时间复杂度过高的低效算法也可能导致有生之年系列。

在分析一般算法的效率时，主要关注两种复杂度

  1. 最坏情况复杂度

$$T_{worst}(n)$$

2.平均复杂度

$$T_{avg}(n)\leq T_{worst}(n)$$

算法复杂度的渐进表示法

其中 log 是对数上面数学基础讲了
n log n 就是 n×log n

函数 1 2 4 8 16 32
1 1 1 1 1 1 1
log n 0 1 2 3 4 5
n 1 2 4 8 16 32
n log n 0 2 8 24 64 160
$$n^2$$ 1 4 16 64 256 1024
$$n^3$$ 1 8 64 512 4096 32768
$$2^n$$ 2 4 16 256 65536 很大
n!(n 乘阶） 1 2 24 40326 很大 很大

最大子列和问题

算法 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int MaxSubseqSuml(int A[], int N){
    int ThisSum, MaxSum = 0;
    int i, j, k;
    for(i = 0; i < N; i ++){
        for(j = i; j < N; j++){
            ThisSum = 0;
            for(k = i; k <= j; k ++){
                ThisSum += A[k];
            }
            if(THisSum > MaxSum){
                MaxSum = ThisSum;
            }
        }
    }
}
算法复杂度是n³，三层for循环。最简单的判断方法。

算法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int MaxSubseqSum2(int A[], int N){
    int ThisSum, MaxSum = 0;
    int i, j;
    for(i = 0; i < N; i ++){
        ThisSum = 0;
        for(j = i; j < N; j++){
            if(ThisSum > MaxSum){
                MaxSum = ThisSum;
            }
        }
    }
    return MaxSum;
}

复杂度为n²，两个for

算法三：

分而治之

这里是实现了一段分而治之的代码
复杂度是 n log n，我的理解就是比如 n = 8
那么就是 8 log 8 = 8 × 2³ = 64；

算法四：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int MaxSubseqSum4(int A[], int n){
    int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0; // 连续赋值是不好的
    for(i = 0; i < N; i++){
        ThisSum += A[i];
        if(ThisSum > MaxSum){
            MaxSum = ThisSum;
        }else if(ThisSum < 0){ // 这段比较重要，判断和是不是负数，如果是负数，那么就归零。
            ThisSum = 0;
        }
    }
    return MaxSum;
}

这段代码看懂了，复杂度是N遍历一次就完了