week 3
才发现latex有显示问题，不管了先这样吧orz
Algorithms
复杂度
渐进符号 asymptotic notation
用 $O$ 表示程序运行时间
只关注最高阶项（对程序影响最大）
$O$ 为运行时间上界
$\Omega$ 为下界
当 $O$ 和 $\Omega$ 相等的时候使用 $\Theta$
e.g.在正序数组中找到某个数字
线性搜索 linear search
直接从从左向右查找。
复杂度 $O(n)$ $\Omega(1)$
二分查找 binary search
$O(log n)$ $\Omega(1)$
在数据随机时无效——考虑使用前提和成本
more details
线性查找(暴力)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| search.c
#include <stdio.h>
int main(void)
{
int numbers[] = {20, 500, 10, 5, 100, 1, 50};
int n;
scanf("%d", &n);
for (int i = 0; i < 7; i++)
{
if (numbers[i] == n)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
}
|
常见问题：
1
2
3
4
5
6
7
8
9
10
11
| for (int i = 0; i < 7; i++)
{
if (numbers[i] == n)
{
printf("Found\n");
}
else
{
printf("Not found\n");
}
}
|
只要数字不等于n,就会直接输出”Not found”
1
2
3
4
5
6
7
8
| for (int i = 0; i < 7; i++)
{
if (numbers[i] == n)
{
printf("Found\n");
}
}
printf("Not found\n");
|
无论是否找到，最后都会输出”Not found”
查找相同字符串
这个程序的问题在哪里？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| search.c
char strings[][10] = {"battleship", "boot", "cannon", "iron", "thimble", "top hat"};
char s[10];
scanf("%s", s);
for (int i = 0; i < 6; i++)
{
if (strings[i] == s)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
return 1;
|
“==”不能用于比较字符串
修改:
1
| if (strcmp(strings[i], s) == 0)
|
查找电话号码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| phonebook.c
#include <stdio.h>
#include <string.h>
int main(void)
{
char names[][10] = {"David", "John", "Yuliia"};
char numbers[][20] = {"+1-xxx-xxx-xxxx", "+1-yyy-yyy-yyyy", "+1-zzz-zzz-zzzz"};
char name[10];
scanf("%s", name);
for (int i = 0; i < 3; i++)
{
if (strcmp(names[i], name) == 0)
{
printf("%s\n", numbers[i]);
return 0;
}
}
printf("Not found\n");
return 1;
}
|
使用多个数组存储信息很麻烦->创建结构体
1
2
3
4
5
| typedef struct
{
char name[10];
char number[20];
} person;
|
排序 sorting
选择排序 selection sort
找到未排序的最小数字，和未排序的队首元素交换
$\Theta(n^2)$
more details
冒泡排序 Bubble sort
重复遍历整个队列，将不符合排序规则的相邻元素交换，直到整个队列完成排序。
(循环退出条件：没有交换产生)
$O(n^2)$ $\Omega(n)$
more details
归并排序 Merge sort
分段排序之后合并。合并：从左向右同时遍历两个数组，将更小的元素依次放进新的数组中。思想类似二分。
$O(n log n)$
课程里老师点亮数字实际上是一种标记，可以用bool flag[]数组实现
more details
递归 recursion
二分就可以用递归实现
引用一个我初学时很喜欢的定义，出自紫书（刘汝佳的《算法竞赛入门经典》）：
递归的定义如下：
递归：
参见“递归”
什么？这个定义什么也没有说啊！好吧，改一下：
递归：
如果还是没明白递归是什么意思，参见“递归”。
还有google的递归笑话：
打印金字塔（非递归版本）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| iteration.c
#include <stdio.h>
void draw(int n);
int main(void)
{
int height;
scanf("%d", &height);
draw(height);
}
void draw(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i + 1; j++)
{
printf("#");
}
printf("\n");
}
}
|
递归版本：
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
| recursion.c
#include <stdio.h>
void draw(int n);
int main(void)
{
int height;
scanf("%d", &height);
draw(height);
}
void draw(int n)
{
if (n == 0)
{
return;
}
draw(n - 1);
printf("%d", n);
for (int i = 0; i < n; i++)
{
printf("#");
}
printf("\n");
}
|
其他
- 推荐书目：《啊哈！算法》对算法的讲解很清晰，我的入门书
还记得第一次看冒泡排序，看了两三遍才彻底明白，当时觉得这个东西好巧妙（因为当时连编程的思维都没有，看代码也很吃力），看完明白了却也记不太住。现在再一看这个觉得简直太简单，简单直接而且复杂度很高很麻烦，几乎就是很暴力的解决问题，代码也一目了然。感叹时间的神奇