[TOC]
数据结构研究组织大量数据的方法，算法分析是对算法运行时间的评估
1. 绪论
在程序正确运行前提下，保证在大量数据集或者特殊情况下能够运行并得出正确结果
1.1 进行算法分析目的
1.1.1 适应大量数据情况
由于简单选择排序，冒泡排序，插入排序的时间复杂度都是 $O(n^2)$ 。只要基于此思想，时间复杂度都不会低，如后例：
从 $N$ 个数中选择第 $k$ 大的数
递减排序，取第K大的数
冒泡排序
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
|
void Bubble_Sort(int a[],int n){
bool flag = false;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= n-i;++j){
if(a[j] < a[j+1]){
swap(a[j],a[j+1]);
flag = true;
}
}
if(flag == false)
return ;
}
}
void Select_Sort(int a[],int n){
for(int i = 1;i <= n;i++){
int maxIdx = i;
for(int j = i+1;j <= n;++j){
if(a[j] > a[maxIdx])
maxIdx = j;
}
if(maxIdx != i)
swap(a[maxIdx],a[i]);
}
}
void KBig(int a[],int n,int k){
Bubble_Sort(a,n);
Select_Sort(a,n);
return a[k];
}
|
插入排序思想
取前 $K$个数递减排序。再取新数 $x_i$ ，从第一个数开始比较
- $x_i \ge a_i$ ：则将该数插入
- $x_i < a_k$ ：则不做操作
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
|
void Direct_InsertSort(ElemType A[], int k){
int i,j;
for(i = 2;i <= k;++i){
if(A[i] > A[i-1]){
A[0] = A[i];
for(j = i-1;j >= 0 && A[0] > A[j];--j)
A[j+1] = A[j];
A[j+1] = A[0];
}
}
}
int KBig_Insert(int a[],int n,int k){
Direct_InsertSort(a,k);
for(int i = k+1;i <= n;++i){
if(a[i] > a[k]){
a[0] = a[i];
for(int j = k;j >= 0 && a[0] > a[j];--j)
a[j+1] = a[j];
a[j+1] = a[0];
}
}
return a[k];
}
int main(){
int n;
int a = (int *)malloc(sizeof(int)*(n+1));
for(int i = 1;i <= n;++i){
...
}
KBig_Insert(a,n,k);
return 0;
}
|
1.1.2 边界条件正确
2.1 数学知识复习
2.1.1 指数
2.1.2 对数
在计算机中，除非特别声明，所有对数都是以2为底的
2.1.3 级数
几何级数
有是否收敛的区别
由等比数列求和
证明：
证明：
算术级数
可以通过基本公式计算值
SP：
2.1.4 模运算
A与B模N同余，记为如：
性质
2.1.5 证明方法
归纳法
- 证明基准情形
- 归纳假设：假设定力对直到某个有限数k的所有情况都成立，在通过这个假设证明后续值成立。
斐波那契数列
证明：证明：
反证法
1.3 递归简论
四条基本法则
- 基准情形：某些基准情形，无需递归就能解出
- 不断推进：每次递归调用，必须向基准情形推进（不能出现循环定义）
- 设计法则：假设所有递归调用都能运行
- 合成效益法则：不同递归调用做不同的工作，避免重复计算
1
2
3
4
5
6
| void printOut(unsigned int N){
if(N >= 10)
printOut(N/10);
printDigit(N-(N/10)*10);
}
|
练习题
1.3 只使用处理IO的 PrintDigit 函数，编写一个可以输出任意实数的函数
由于实数用计算机表示会存在舍入误差(RoundUp)，所以在输出前，需按照舍入策略进行舍入。
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>
using namespace std;
double RoundUp(double N,int DecPlaces){
int i;
double AmountToAdd = 0.5;
for(i = 0;i < DecPlaces;++i)
AmountToAdd /= 10;
return N+AmountToAdd;
}
void PrintFractionPart(double FractionPart,int DecPlaces){
int i,ADigit;
for(i = 0;i < DecPlaces;++i){
FractionPart *= 10;
ADigit = (int)FractionPart;
cout << ADigit;
FractionPart = FractionPart - ADigit;
}
}
void PrintReal(double N,int DecPlaces){
int IntPart;
double FractionPart;
if(N < 0){
putchar('-');
N = -N;
}
N = RoundUp(N,DecPlaces);
IntPart = (int)N;
FractionPart = N-IntPart;
cout << IntPart;
if(DecPlaces > 0)
putchar('.');
PrintFractionPart(FractionPart,DecPlaces);
}
int main(){
cout << "输入需要输出的实数:";
double N;
cin >> N;
cout << "输入小数点后位数:";
int DecPlaces;
cin >> DecPlaces;
PrintReal(N,DecPlaces);
return 0;
}
|
1.4 语言提供 #include filename 的语句，用于读入 filename ，并将它插入到 include 语句处
- 文件本身还可以包含
#include 语句- 不能
include 自身(self-referential)
思路：
逐行检测源代码，是否存在 #include SomeFile
检查 list 中，是否有文件名 SomeFile
- 有，则
continue - 无：
- 调用
ProcessFile(SomeFile); ，将文件内容插入当前位置； - 将
SomeFile 入 list
list 列表，维护由 ProcessFile 处理过的文件，避免重复调用
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
61
| # include<iostream>
# include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main(int argc, char const *argv[]){
FILE *fp = fopen("source.txt", "w+");
fputs("#include <filename1>\n", fp);
fputs("#include <filename1>\n", fp);
fputs("#include <filename2>\n", fp);
fputs("#include <filename3>\n", fp);
fputs("#include <filename3>\n", fp);
fputs("\n", fp);
fputs("int main(){\n", fp);
fputs(" cout << 'Hello' <<endl;\n", fp);
fputs(" return 0;\n", fp);
fputs("};\n", fp);
rewind(fp);
vector<string> list;
char str[1024];
char st[1024];
string tmp;
while(fgets(str, 1024, fp) && !feof(fp)){
tmp = str;
tmp.erase(remove_if(tmp.begin(), tmp.end(), [](char c) {
return (c == ' ');
}), tmp.end());
if('#' == str[0]){
string filename = tmp.substr(tmp.find('<')+1,tmp.find('>')-tmp.find('<')-1);
vector<string>::iterator idx = find(list.begin(),list.end(),filename);
if(list.end() == idx){
cout << str;
list.push_back(filename);
FILE *fo = fopen((filename+".txt").data(), "r");
while(fgets(st, 1024, fo)){
string stt = st;
cout << stt;
}
cout << endl;
}else{
continue;
}
}else{
cout << str;
}
}
fclose(fp);
return 0;
}
|
1.5 证明公式
$log_2X0$ 成立
证明：
| | $logX$ | $X$ |
|:—-:|:—-:|:—-:|
|$(0,1]$|$\le 0$ | $>0$ |
| $(1,2]$ | $\le 1$ | >1 |
|$(2,4]$| $\le 2$ | $>2$ |
| $(p,2p]$ | $\le p$ | $>p$ |
1.6 级数求和
$\sum_{i=0}^{\infty}\limits \frac{1}{4^i}$
$\sum_{i=0}^{\infty}\limits \frac{i}{4^i}$
$\sum_{i=0}^{\infty}\limits \frac{i^2}{4^i}$
d. 太复杂，思路就是上述解法不断迭代
1.7 估计$\sum_{i=\lfloor\frac{N}{2}\rfloor}^N\limits\frac{1}{i}$
$S=\sum_{i=1}^N-\sum_1^{i=\lfloor\frac{N}{2}\rfloor-1}\limits\frac{1}{i}=lnN-ln\frac{N}{2}\approx ln2$
1.8 $2^{100}\left(mod\quad5\right)$
1.9 令 $F_i$ 为斐波那契数，证明
$F_0=1,F_1=1,F_2=2,F_m=F_{m-1}+F_{m-2}$
$\sum_{i=1}^{N-2}\limits F_i=F_N-2$
归纳法：
$F_N<\phi^N,其中\phi=\frac{1+\sqrt{5}}{2}$
1.10 证明公式
$\sum_{i=1}^{N}\limits(2i-1)=N^2$
$\sum_{i=1}^{N}\limits i^3=\left(\sum_{i=1}^N\limits i\right)^2$
归纳法证明：