数据结构学习一

学习数据结构笔记

数学基础

指数和对数

指数函数

$$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遍历一次就完了