数据结构复习 查找

查找表是由同一类型的数据元素(或记录)组成的集合。

查找表的分类:

1.静态查找表:仅作查询和检索操作的查找表

2.动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除某个已存在的数据元素

关键字:是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。若此关键字可以识别唯一的一个记录,则称之为“主关键字”。若此关键字能识别若干记录,则称之为“次关键字”。

查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或记录。

若查找表中存在这样的一个记录,则”查找成功“,查找结果:给出整个记录的信息,或指示该记录在查找表中的位置。否则”查找不成功“,查找结果:给出“空记录”或“空指针”。

查找的方法取决于查找表的结构。由于查找表的数据元素之间不存在明显的组织规律,因此不便于查找。为了提高查找的效率,需要在查找表的元素之间人为地附加某种确定的关系。也就是说,用另外一种结构来表示查找表。

查找方法评价:查找速度、占用存储空间多少、算法本身复杂程度、平均查找长度ASL(Average Search Length,为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值)

img

img

静态查找表:

1.顺序表的查找:

查找过程:从表的一端开始,逐个进行记录的关键字与给定值的比较。

例如,有n个数,则构造一个长度为n+1的数组arr,其中arr[0]为监视哨,存放要查找的元素,剩下的1~n位存放n个数。从arr[n]开始向arr[1]查找,则比较次数:

若查找第n个元素,则比较1次(第一次就找到);

若查找第n-1个元素,则比较2次(第一次比较之后,又比较了一次);

若查找第i个元素,则比较(n+1-i)次;

查找失败:比较了n+1次。

1
2
3
4
5
6
7
int Search_Seq(int &a[], int key){
a[0] = key;
for(int i = n; i >= 1; --i)
if(a[i] == key)
return i;
return 0;
}

对于顺序表,等概率情况下:=img

若不等概率,或查找概率无法事先确定,则采取的改进方法是:在每次查找之后,将刚刚查找过的记录移至表尾位置上。

2.有序表的查找:

顺序表的查找算法简单,但是ASL较大,不适用于表长较大的查找表。

若以有序表表示静态查找表,则查找过程可以“折半”进行。

折半查找:

查找过程:每次将待查记录所在区间减小一半。

适用条件:采用顺序存储结构的有序表。

折半查找算法的实现:

img

若k == mid,查找成功;

若k < mid,high = mid - 1;

若k > mid,low = mid + 1;

重复上述操作,直至条件low <= high不再满足为止。

1
2
3
4
5
6
7
8
9
10
int Search_Bin(int &a[], int k){
int low = 1, high = n;
while(low <= high){
int mid = (low + high) / 2;
if(k == a[mid]) return mid;
else if(k > a[mid]) low = mid + 1;
else high = mid - 1;
}
return 0;
}

性能分析:

判定树:描述查找过程的二叉树。

img

img

img

img

img

由此可见,

  • 折半查找效率比顺序查找高。
  • 折半查找只适用于有序表,并且以顺序存储结构存储。

顺序表和有序表的比较:

顺序表 有序表
表的特性 无序 有序
存储结构 顺序 或 链式 顺序
插删操作 易于进行 需要移动元素
ASL

3.索引顺序表(=索引+顺序表)

在建立顺序表的同时,建立一个索引项,包括:关键字项和指针项。索引表按关键字有序,表则为分块有序。

顺序表:

15 95 42 37 65 16

索引表:

95 0 65 3 85 6

(索引表中包含:第一块:0-2,最大关键字是95,起始是0;…)

索引顺序查找,又称分块查找。

查找过程:将表分为几块,块内无序,块间有序;先确定待查记录所在块,再在块内查找。

适用条件:分块有序表

算法实现:用数组存放待查记录,每个数据元素至少含有关键字域;建立索引表,每个索引表结点含有最大关键字域和指向本块第一个结点的指针。

img

img

查找方法比较:

顺序 折半 分块
ASL 两者之间
表结构 无序 或 有序 有序 分块有序表
存储结构 顺序 或 链式 顺序 顺序 或 链式

从查找性能来看,最好情况能达到O(logn),此时要求表有序;

从插入和删除的性能来看,最好情况能达到O(1),此时要求存储结构是链表。

动态查找表:

特点:表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值的记录,则查找成功,否则插入关键字等于key的记录。

代价函数

二次代价函数(quadratic cost)

image-20200528120907105

其中,C代表代价函数,x代表样本,y表示实际值,a表示输出值,n表示样本的总数。

相当于把误差的平方加起来再除以一个总数。

以一个样本为例:

image-20200528121549753

image-20200528121411995

image-20200528121947827

z表示神经元的输入,σ表示激活函数。w和b的梯度跟激活函数的梯度成正比,激活函数的梯度越大,w和b的大小调整得越快,训练收敛得就越快。假设我们的激活函数是sigmoid函数:

image-20200528143620424

假设我们目标是收敛到1.0。1点为0.82离目标比较远,梯度比较大,权值调整比较大。2点为0.98离目标比较近,梯度比较小,权值调整比较小。调整方案合理。
假如我们目标是收敛到0。1点为0.82目标比较近,梯度比较大,权值调整比较大。2点为0.98离目标比较远,梯度比较小,权值调整比较小。调整方案不合理。

交叉熵代价函数(cross-entropy)

换一个思路,我们不改变激活函数,而是改变代价函数,改用交叉熵代价函数:

image-20200528123023183

其中,C代表代价函数,x代表样本,y表示实际值,a表示输出值,n表示样本的总数。

image-20200528123222414image-20200528123254307

image-20200528123309837

对于交叉熵代价函数:(输出值即为预测值)

image-20200528123622492

(S型函数,如sigmoid函数、双曲正弦等等)

对数似然代价函数(log-likelihood cost)

对数似然函数常用来作为softmax回归的代价函数,如果输出层神经元是sigmoid函数,可以采用交叉熵代价函数。而深度学习中更普遍的做法是将softmax作为最后一层,此时常用的代价函数是对数似然代价函数。

对数似然代价函数与softmax的组合和交叉熵与sigmoid函数的组合非常相似。对数似然代价函数在二分类时可以简化为交叉熵代价函数的形式。

在Tensorflow中,用:

1
2
tf.nn.sigmoid_cross_entropy_with_logits()来表示跟sigmoid搭配使用的交叉熵
tf.nn.softmax_cross_entropy_with_logits()来表示跟softmax搭配使用的交叉熵

关于softmax函数和sigmoid函数,可参考:

https://cloud.tencent.com/developer/article/1092667

1.Sigmoid函数

Sigmoid函数是一个在生物学中常见的S型的函数,也称为S型生长曲线。Sigmoid函数常被用作神经网络的阈值函数,将变量映射到0,1之间。

1.1公式

image-20200528142355314

其对x的导数可以用自身表示:

image-20200528142519308

1.2python实现

1
2
3
4
import numpy as np
import matplotlib.pyplot as plt
def sigmoid(x):
return 1.0/(1+np.exp(-x))

1.3函数图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import numpy as np
import matplotlib.pyplot as plt
def sigmoid(x):
return 1.0/(1+np.exp(-x))

sigmoid_inputs = np.arange(-10,10)
sigmoid_outputs=sigmoid(sigmoid(sigmoid_inputs))
print("Sigmoid Function Input :: {}".format(sigmoid_inputs))
print("Sigmoid Function Output :: {}".format(sigmoid_outputs))

plt.plot(sigmoid_inputs,sigmoid_outputs)
plt.xlabel("Sigmoid Inputs")
plt.ylabel("Sigmoid Outputs")
plt.show()

image-20200528142712145

2.softmax函数

在数学,尤其是概率论和相关领域中,softmax函数,或称归一化指数函数
,是逻辑函数的一种推广。它能将一个含任意实数的K维的向量z的“压缩”到另一个K维实向量σ(z) 中,使得每一个元素的范围都在(0,1)之间,并且所有元素的和为1。

2.1公式

image-20200528143027539

在多项逻辑回归和线性判别分析中,函数的输入是从K个不同的线性函数得到的结果,而样本向量 x 属于第 j 个分类的概率为:

image-20200528143059592

这可以被视作K个线性函数x→xTw1,…,→xTwK softmax函数的复合(xTwxw)

2.2python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np

def softmax(x):
orig_shape=x.shape
if len(x.shape)>1:
#Matrix
#shift max whithin each row
constant_shift=np.max(x,axis=1).reshape(1,-1)
x-=constant_shift
x=np.exp(x)
normlize=np.sum(x,axis=1).reshape(1,-1)
x/=normlize
else:
#vector
constant_shift=np.max(x)
x-=constant_shift
x=np.exp(x)
normlize=np.sum(x)
x/=normlize
assert x.shape==orig_shape
return x

2.3函数图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def softmax(x):
orig_shape=x.shape
if len(x.shape)>1:
#Matrix
#shift max whithin each row
constant_shift=np.max(x,axis=1).reshape(1,-1)
x-=constant_shift
x=np.exp(x)
normlize=np.sum(x,axis=1).reshape(1,-1)
x/=normlize
else:
#vector
constant_shift=np.max(x)
x-=constant_shift
x=np.exp(x)
normlize=np.sum(x)
x/=normlize
assert x.shape==orig_shape
return x

softmax_inputs = np.arange(-10,10)
softmax_outputs=softmax(softmax_inputs)
print("Sigmoid Function Input :: {}".format(softmax_inputs))
print("Sigmoid Function Output :: {}".format(softmax_outputs))
# 画图像
plt.plot(softmax_inputs,softmax_outputs)
plt.xlabel("Softmax Inputs")
plt.ylabel("Softmax Outputs")
plt.show()

image-20200528143302951

hdu4576

题目

一个圆盘,有n个编号(1,2,3……n),从1出发,每次能逆时针或顺时针走w步,问经过m次后,最终停留在区间[l,r]的概率。

解析

首先,取模运算是一定要把1到n换成0到n-1;其次,利用temp来进行奇偶变换。

引用自博客:

https://www.cnblogs.com/kevinACMer/p/3723531.html

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 1000005
int n, m, l, r;
double dp[205][2];
int w[maxn];
int main(){
while(scanf("%d%d%d%d", &n, &m, &l, &r) && (n || m || l || r)){
for(int i = 0; i < m; ++i) scanf("%d", &w[i]);
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int cur = 0;
for(int j = 0; j < m; ++j){
int t = w[j] % n;
cur ^= 1;
for(int i = 0; i < n; ++i)
dp[i][cur] = 0.5 * dp[(i + t) % n][cur ^ 1] + 0.5 * dp[(i - t) % n][cur ^ 1];
}
double ans = 0;
for(int i = l - 1; i < r; ++i) ans += dp[i][cur];
printf("%.4lf\n", ans);
}
return 0;
}

hdu1024

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1024

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
#define FI(a, b, c) for(int a = (b); a <= (c); a++)
#define FD(a, b, c) for(int a = (b); a >= (c); a--)
using namespace std;

int n, m, t;
long long d[1000005], l[1000005];

int main(){
while(scanf("%d %d", &m, &n) != EOF){
FI(i, 1, m) d[i] = l[i] = -1e15;

while(n--){
scanf("%d", &t);
FD(i, m, 1){
d[i] = max(d[i], l[i - 1]) + t;
l[i] = max(l[i], d[i]);
}
}
printf("%lld\n", l[m]);
}
}

高度为h的AVL树的最少节点数

设高度为h的AVL树最少的节点数为f(h)
可以算出f(0)=0,f(1)=1,f(2)=2.
设左子树的高度为h-1,则右子树的高度为h-2.
因此得到递推公式:f(h) = f(h-1) + f(h-2) + 1.

Hash

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.