数据结构与算法学习笔记1

程序性能

空间复杂性

程序所需要的空间主要由以下部分构成:

指令空间(instruction space)指令空间是指用来存储经过编译之后的程序指令所需的空间。

数据空间(data space)数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成:

  1. 存储常量和简单变量所需要的空间:如4是常量,a、b、c是简单变量。

    1
    2
    3
    4
    int example(int a, int b, int c)
    {
    return a + b + c + 4;
    }
  2. 存储复合变量所需要的空间。这一类包括数据结构所需的空间及动态分配的空间。如数组a。

    1
    2
    3
    4
    5
    6
    7
    int example(int a[], int n)
    {
    int sum = 0;
    for(int i = 0; i < n; i++)
    sum += a[i];
    return sum;
    }

环境栈空间(environment stack space)环境栈用来保存函数调用返回时恢复运行所需要的信息。例如,如果函数fun1调用了函数fun2,那么至少必须保存fun2结束时fun1将要继续执行的指令的地址。

指令空间

程序所需要的指令空间的数量取决于如下因素:

把程序编译成机器代码的编译器

编译时实际采用的编译器选项

目标计算机

数据空间

对于简单变量和常量来说,所需要的空间取决于所使用的使用的计算机和编译器以及变量与常量的数目。

环境栈

当一个函数被调用时,下面的数据将被保存在环境栈中:

返回地址

函数被调用时所有局部变量的值以及传值形式参数的值

所有引用参数及常量引用参数的定义

1
2
3
4
5
6
7
template <class T>
T Rsum(T a[], int n)
{
if(n > 0)
return Rsum(a, n - 1) + a[n - 1];
return 0;
}

当Rsum被调用时,不管该调用是来自外部或第4行,a的当前赋值、n的值以及程序运行结束时的返回地址都被存储在环境栈之中。

值得注意的是,有些编译器在保留局部变量的值、传值形式参数的值以及引用参数和常量引用参数的定义时,对于递归函数和非递归函数一视同仁,而有些编译器则仅为递归函数保存上述内容。所以实际使用的编译器将影响环境栈所需要的空间。

可以把一个程序所需要的空间分成两部分:

固定部分:它独立于实例的特征。一般包含指令空间、简单变量和常量及定长复合变量所占空间等等。

可变部分:包含复合变量所需空间(这些变量的大小依赖于所解决的具体问题)、动态分配的空间(一般都依赖于实例特征)、递归栈所需空间(也依赖于实例特征)。

任意程序P所需要的空间S(P)可以表示为:

其中c是一个常量,表示固定部分所需要的空间, Sp表示可变部分所需要的空间。

1
2
3
4
5
6
7
8
template <class T>
int seq_search(T a[], const T& x, int n)
{
int i;
for(i = 0; i < n && a[i] != x; i++);
if(i == n) return -1;
return i;
}

我们希望采用实例特征n来估算该函数的空间复杂性。假定T为int类型,则数组a中的每个元素需要2个字节,实参x需要2个字节,传值形式参数n需要2个字节,局部变量i需要2个字节,每个整型常量0和-1也分别需要2个字节。因此,所需要的总的数据空间为12字节。因为该空间独立于n,所以S(n) = 0。

1
2
3
4
5
6
7
8
template <class T>
T Sum(T a[], int n)
{
T tsum = 0;
for(int i = 0; i < n; i++)
tsum += a[i];
return tsum;
}

在该函数中,a、n、i和tsum需要分配空间,所以程序所需要的空间与n无关,因此有S(n) = 0。

1
2
3
4
5
int factorial(int n)
{
if(n <= 1) return 1;
else return n * factorial(n - 1);
}

该程序的空间复杂性是n的函数而不是输入(只有一个)或输出(也只有一个)个数的函数。递归深度为max{n, 1}。每次调用函数Factorial 时,递归栈需要保留返回地址( 2个字节)和n的值(2个字节)。此外没有其他依赖于n的空间,所以S(n) = 4*max{n, 1}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 使用递归函数生成排列
void Perm(T list[], int k, int m)
{
int i;
if(k == m)
{
for(i = 1; i <= m; i++)
cout << list[i] << " ";
cout << endl;
}
else
{
for(i = k; i <= m; i++)
{
swap(list[k], list[i]);
Perm(list, k + 1, m);
swap(list[k], list[i]);
}
}
}

对于初始调用Perm(list, 0, n-1),递归的深度为n。由于每次调用需要10个字节的递归栈空间(每个返回地址、list、k、m以及i各需要2个字节),所以需要10n字节的递归栈空间,S(n) = 10n。

时间复杂性

有两个更可行的方法可以用来估算运行时间:

  1. 确定关键操作所需要的执行时间;
  2. 确定程序执行的总步数。

操作计数

1
2
3
4
5
6
7
8
9
10
// 计算名次
void Rank(T a[], int n, int r[])
{
for(int i = 0; i < n; i++)
r[i] = 0;
for(int i = 1; i < n; i++)
for(int j = 0; j < i; j++)
if(a[j] >= a[i]) r[j]++;
else r[i]++;
}

注意在估算时间复杂性时没有考虑for循环的额外开销、初始化数组r的开销以及每次比较a中两个元素时对r进行增值的开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 原地重排
void rearrange()
{
// rank: r[], array: a[]
// int r[5] = {2, 0, 4, 1, 3};
// int a[5] = {4, 3, 9, 3, 7};
for(int i = 0; i < 5; i++)
{
while(r[i] != i)
{
int t = r[i];
swap(a[t], a[i]);
swap(r[t], r[i]);
}
}
}

执行步数

程序步(program step)可以定义为一个语法或语义意义上的程序片段,该片段的执行时间独立于实例特征。

线段树

基本概念

线段树(segment tree)是一种二叉搜索树,它的每一个结点对应着一个区间 [L, R],叶子结点对应的是一个单位区间,即 L == R。对于一个非叶子结点 [L, R],它的左儿子所表示的区间为 [L, (L + R) / 2],右儿子所表示的区间为 [(L + R) / 2 + 1, R] (也可以用位运算,更快:[L, (L + R) >> 1] 和 [((L + R) >> 1) | 1, R])。根据定义,线段树是一棵平衡二叉树,它的叶子结点数目为 N,即整个区间的长度。

基本操作

树状数组

什么是树状数组?

就是用数组来模拟树形结构,可以解决大部分基于区间上的更新以及求和问题。树状数组可以解决的问题都可以用线段树解决,这两者的区别在哪里呢?树状数组修改和查询的复杂度都是 O(log n),而且相比线段树系数要少很多,比传统数组要快,而且容易写。缺点是遇到复杂的区间问题还是不能解决,功能还是有限。树状数组多用于高效计算数列的前缀和。

核心思想

(1) 树状数组中的每个元素是原数组中的一个或多个连续元素的和;

(2) 在进行连续求和时,只需要将树状数组中某几个元素进行求和;

(3) 在对某一个元素进行修改时,只需要修改树状数组中某几个元素的和即可。

(4) 用 A 表示原始数组,C 表示树状数组,则:C[i] = A[i - 2^k + 1] + A[i - 2^k + 2] + … + A[i];k为 i 的二进制中末尾连续的 0 的个数。

C[1] = A[1];

C[2] = A[1] + A[2];

C[3] = A[3];

C[4] = A[1] + A[2] + A[3] + A[4];

C[5] = A[5];

C[6] = A[5] + A[6];

C[7] = A[7];

C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

(5) C 中元素的后继(为此结点的父结点):结点的后继是比它大、最近的且编号末尾连续 0 比它多的结点。

(6) C 中元素的前驱:结点的前驱为比它小、最近的且末尾连续 0 的个数比它多的结点。前驱主要用来计算连续和。

例如 i = 8(1000) 时候,k = 3,可自行验证。

这个怎么实现求和呢,比如我们要找前 7 项和,那么应该是 SUM = C[7] + C[6] + C[4];

而根据上面的式子,容易的出 SUM[i] = C[i] + C[i - 2 ^ k1] + C[(i - 2 ^ k1) - 2 ^ k2] + …..;

其实树状数组就是一个二进制上面的应用。

现在新的问题来了:2 ^ k 该怎么求呢,不难得出 2 ^ k = i & (i ^ (i - 1));但这个还是不好求出呀,于是就有:2 ^ k = i & (- i);

为什么呢?

这里利用的负数的存储特性,负数是以补码存储的,对于整数运算 x & (-x) 有:

当 x 为 0 时,即 0 & 0,结果为 0;

当 x 为奇数时,最后一个比特位为 1,取反加 1 没有进位,故 x 和 - x 除最后一位外前面的位正好相反,按位与结果为 0。结果为 1。

当 x 为偶数,且为 2 的 m 次方时,x 的二进制表示中只有一位是 1(从右往左的第 m + 1 位),其右边有 m 位 0,故 x 取反加 1 后,从右到左第有 m 个 0,第 m + 1 位及其左边全是 1。这样,x & (- x) 得到的就是 x。

当 x 为偶数,却不为 2 的 m 次方的形式时,可以写作 x = y * (2 ^ k)。其中,y 的最低位为 1。实际上就是把 x 用一个奇数左移 k 位来表示。这时,x 的二进制表示最右边有 k 个 0,从右往左第 k + 1 位为 1。当对 x 取反时,最右边的 k 位 0 变成 1,第 k + 1 位变为 0;再加 1,最右边的 k 位就又变成了 0,第 k + 1位因为进位的关系变成了 1。左边的位因为没有进位,正好和 x 原来对应的位上的值相反。二者按位与,得到:第 k + 1 位上为 1,左边右边都为 0。结果为 2 ^ k。

总结一下:x & (-x),当 x 为 0 时结果为 0;x 为奇数时,结果为 1;x 为偶数时,结果为 x 中 2 的最大次方的因子。

而且这个有一个专门的称呼,叫做 lowbit,即取 2 ^ k。

基本操作

1.预备函数 lowbit(int)

树状数组最基本的操作就是找到前驱和后继。lowbit 函数返回将参数转化为二进制后最后一个 1 所在的位置转化为十进制后的值。例如,34 转化二进制为 100010,最后一个 1 在第二位,所以返回 10, 即 2 。

1
2
3
int lowbit(int k){
return k & (-k);
}

2.修改原始数据某一元素的值

将 a[k] 的值增加 v ,需要把 e[k] 以及其后继结点的值全部加 k ,一直到 LEN (数组最大长度)。

1
2
3
4
5
6
7
8
#define LEN 100
int e[LEN];
void add(int k, int v){
while(k < LEN){
e[k] += v;
k += lowbit(k);
}
}

3.求原始数据前 k 项的和

只需要把 e[k] 以及其前驱结点的值累加即可。

1
2
3
4
5
6
7
8
int sum(int k){
int re = 0;
while(k > 0){
re += e[k];
k -= lowbit(k);
}
return re;
}

代码实现

模板题

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int n;
int a[50005],c[50005]; //对应原数组和树状数组

int lowbit(int x){
return x & (-x);
}

void update(int i,int k){ //在i位置加上k
while(i <= n){
c[i] += k;
i += lowbit(i);
}
}

int getsum(int i){ //求A[1 - i]的和
int res = 0;
while(i > 0){
res += c[i];
i -= lowbit(i);
}
return res;
}

int main(){
int t;
cin >> t;
for(int tot = 1; tot <= t; tot++){
cout << "Case " << tot << ":" << endl;
memset(a, 0, sizeof a);
memset(c, 0, sizeof c);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
update(i, a[i]); //输入初值的时候,也相当于更新了值
}

string s;
int x, y;
while(cin >> s && s[0] != 'E'){
cin >> x >> y;
if(s[0] == 'Q'){ //求和操作
int sum = getsum(y) - getsum(x-1); //x-y区间和也就等于1-y区间和减去1-(x-1)区间和
cout << sum << endl;
}
else if(s[0] == 'A'){
update(x, y);
}
else if(s[0] == 'S'){
update(x, -y); //减去操作,即为加上相反数
}
}

}
return 0;
}

树状数组的几种变式(区间更新,区间查询)

1.单点更新、单点查询

2.单点更新、区间查询

3.区间更新、单点查询

这就是第一个问题,如果题目是要把 x - y 区间内的所有值全部加上 k 或者减去 k ,然后查询操作是问某个点的值。如果是像上面的树状数组来说,就必须把 x - y 区间内每个值都更新,这样的复杂度肯定是不行的,这个时候,就不能再用数据的值建树了,这里我们引入差分,利用差分建树。

假设我们规定 A[0] = 0,则有 A[i] = ΣD[j] (D[j] = A[j] - A[j - 1])。那么当某个区间 [x, y] 值改变了,区间内的差值是不变的,只有 D[x] 和 D[y + 1] 的值发生改变。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n;
int a[50005] = {0};
int sum1[50005]; //(D[1] + D[2] + ... + D[n])
int sum2[50005]; //(1*D[1] + 2*D[2] + ... + n*D[n])

int lowbit(int x){
return x & (- x);
}

void update(int i, int k){
int x = i; //因为x不变,所以得先保存i值
while(i <= n){
sum1[i] += k;
sum2[i] += k * (x - 1);
i += lowbit(i);
}
}

int getsum(int i){ //求前缀和
int res = 0, x = i;
while(i > 0){
res += x * sum1[i] - sum2[i];
i -= lowbit(i);
}
return res;
}

int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
update(i, a[i] - a[i - 1]); //输入初值的时候,也相当于更新了值
}

//[x,y]区间内加上k
update(x, k); //A[x] - A[x-1]增加k
update(y + 1, - k); //A[y+1] - A[y]减少k

//求[x,y]区间和
int sum = getsum(y) - getsum(x - 1);

return 0;
}

Trie树

字典树

字典树,因为它的搜索快捷的特性被单词搜索系统使用,故又称单词查找树。它是一种树形结构的数据结构。之所以快速,是因为它用空间代替了速度。

性质

1.根节点不包含字符,除根节点外每一个节点都只包含一个字符;

2.从根节点到某一个节点,路径上经过的字符连接起来,就是该节点对应的字符串;

3.每个节点的所有子节点包含的字符都不相同。

应用

1.字符串的快速查找:

给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中,我们可以用数组枚举,用哈希,用字典树,先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。

2.串排序:

给定N个互不相同的仅由一个单词构成的英文名,让你将他们按字典序从小到大输出用字典树进行排序,采用数组的方式创建字典树,这棵树的每个节点的所有儿子很显然地按照其字母大小排序,对这棵树进行先序遍历即可。

3.最长公共前缀:

对所有串建立字典树,对于两个串的最长公共前缀的长度即他们所在的节点的公共祖先个数,于是,问题就转化为最近公共祖先问题。

算法实现

1
2
3
4
5
6
//结点的结构体构建
//假设所有字母均为小写英文字母
struct Node{
Node * ch[26];
int num;
};
1
2
3
4
5
6
Node a[N], * root, * ap;
Node * newnode(){
memset(ap->ch, 0, sizeof(ap->ch));
ap->num = 0;
return ap++;
}

向字典树中插入一个字符串:

1
2
3
4
5
6
7
8
9
10
11
void Insert(char * s){
Node * cur = root;
cur->num++;
while(* s != '\0'){
int t = * (s++) - 'a';
if(cur->ch[t] == NULL)
cur->ch[t] = newnode();
cur = cur->ch[t];
cur->num++;
}
}

在 main 函数中,要初始化和清空字典树:

1
2
ap = a;
root = newnode();

例题

模板题1

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 500000;

struct node{
node * ch[26];
int num;
}a[N], * root;

char s[11];
int p = 0;

node * newNode(){
memset(a[p].ch, 0, sizeof(a[p].ch));
a[p].num = 0;
return &a[p++];
}

void Insert(char * s){
node * cur = root;
cur->num++;
while(* s != '\0'){
int t = * (s++) - 'a';
if(cur->ch[t] == NULL)
cur->ch[t] = newNode();
cur = cur->ch[t];
cur->num++;
}
}

int getans(char * s){
node * cur = root;
while(* s != '\0'){
int t = * (s++) - 'a';
if(cur->ch[t] == NULL) return 0;
cur = cur->ch[t];
}
return cur->num;
}

int main(){
root = newNode();
gets(s);
while(s[0] != '\0'){
Insert(s);
gets(s);
}
while(~scanf("%s", s)){
printf("%d\n", getans(s));
}
return 0;
}

模板题2

1

数据结构复习 查找

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

查找表的分类:

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的记录。

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