forked from jas0n1ee/SketchofD-A
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sketch ofDandA.html
1501 lines (1366 loc) · 56.3 KB
/
Sketch ofDandA.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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>Sketch ofD&A_Total</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
/* GitHub stylesheet for MarkdownPad (http://markdownpad.com) */
/* Author: Nicolas Hery - http://nicolashery.com */
/* Version: b13fe65ca28d2e568c6ed5d7f06581183df8f2ff */
/* Source: https://github.com/nicolahery/markdownpad-github */
/* RESET
=============================================================================*/
html, body, div, span, applet, object, iframe, h1, h2, h3, h4, h5, h6, p, blockquote, pre, a, abbr, acronym, address, big, cite, code, del, dfn, em, img, ins, kbd, q, s, samp, small, strike, strong, sub, sup, tt, var, b, u, i, center, dl, dt, dd, ol, ul, li, fieldset, form, label, legend, table, caption, tbody, tfoot, thead, tr, th, td, article, aside, canvas, details, embed, figure, figcaption, footer, header, hgroup, menu, nav, output, ruby, section, summary, time, mark, audio, video {
margin: 0;
padding: 0;
border: 0;
}
/* BODY
=============================================================================*/
body {
font-family: Helvetica, arial, freesans, clean, sans-serif;
font-size: 14px;
line-height: 1.6;
color: #333;
background-color: #fff;
padding: 20px;
max-width: 960px;
margin: 0 auto;
}
body>*:first-child {
margin-top: 0 !important;
}
body>*:last-child {
margin-bottom: 0 !important;
}
/* BLOCKS
=============================================================================*/
p, blockquote, ul, ol, dl, table, pre {
margin: 15px 0;
}
/* HEADERS
=============================================================================*/
h1, h2, h3, h4, h5, h6 {
margin: 20px 0 10px;
padding: 0;
font-weight: bold;
-webkit-font-smoothing: antialiased;
}
h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
font-size: inherit;
}
h1 {
font-size: 28px;
color: #000;
}
h2 {
font-size: 24px;
border-bottom: 1px solid #ccc;
color: #000;
}
h3 {
font-size: 18px;
}
h4 {
font-size: 16px;
}
h5 {
font-size: 14px;
}
h6 {
color: #777;
font-size: 14px;
}
body>h2:first-child, body>h1:first-child, body>h1:first-child+h2, body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
margin-top: 0;
padding-top: 0;
}
a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
margin-top: 0;
padding-top: 0;
}
h1+p, h2+p, h3+p, h4+p, h5+p, h6+p {
margin-top: 10px;
}
/* LINKS
=============================================================================*/
a {
color: #4183C4;
text-decoration: none;
}
a:hover {
text-decoration: underline;
}
/* LISTS
=============================================================================*/
ul, ol {
padding-left: 30px;
}
ul li > :first-child,
ol li > :first-child,
ul li ul:first-of-type,
ol li ol:first-of-type,
ul li ol:first-of-type,
ol li ul:first-of-type {
margin-top: 0px;
}
ul ul, ul ol, ol ol, ol ul {
margin-bottom: 0;
}
dl {
padding: 0;
}
dl dt {
font-size: 14px;
font-weight: bold;
font-style: italic;
padding: 0;
margin: 15px 0 5px;
}
dl dt:first-child {
padding: 0;
}
dl dt>:first-child {
margin-top: 0px;
}
dl dt>:last-child {
margin-bottom: 0px;
}
dl dd {
margin: 0 0 15px;
padding: 0 15px;
}
dl dd>:first-child {
margin-top: 0px;
}
dl dd>:last-child {
margin-bottom: 0px;
}
/* CODE
=============================================================================*/
pre, code, tt {
font-size: 12px;
font-family: Consolas, "Liberation Mono", Courier, monospace;
}
code, tt {
margin: 0 0px;
padding: 0px 0px;
white-space: nowrap;
border: 1px solid #eaeaea;
background-color: #f8f8f8;
border-radius: 3px;
}
pre>code {
margin: 0;
padding: 0;
white-space: pre;
border: none;
background: transparent;
}
pre {
background-color: #f8f8f8;
border: 1px solid #ccc;
font-size: 13px;
line-height: 19px;
overflow: auto;
padding: 6px 10px;
border-radius: 3px;
}
pre code, pre tt {
background-color: transparent;
border: none;
}
kbd {
-moz-border-bottom-colors: none;
-moz-border-left-colors: none;
-moz-border-right-colors: none;
-moz-border-top-colors: none;
background-color: #DDDDDD;
background-image: linear-gradient(#F1F1F1, #DDDDDD);
background-repeat: repeat-x;
border-color: #DDDDDD #CCCCCC #CCCCCC #DDDDDD;
border-image: none;
border-radius: 2px 2px 2px 2px;
border-style: solid;
border-width: 1px;
font-family: "Helvetica Neue",Helvetica,Arial,sans-serif;
line-height: 10px;
padding: 1px 4px;
}
/* QUOTES
=============================================================================*/
blockquote {
border-left: 4px solid #DDD;
padding: 0 15px;
color: #777;
}
blockquote>:first-child {
margin-top: 0px;
}
blockquote>:last-child {
margin-bottom: 0px;
}
/* HORIZONTAL RULES
=============================================================================*/
hr {
clear: both;
margin: 15px 0;
height: 0px;
overflow: hidden;
border: none;
background: transparent;
border-bottom: 4px solid #ddd;
padding: 0;
}
/* TABLES
=============================================================================*/
table th {
font-weight: bold;
}
table th, table td {
border: 1px solid #ccc;
padding: 6px 13px;
}
table tr {
border-top: 1px solid #ccc;
background-color: #fff;
}
table tr:nth-child(2n) {
background-color: #f8f8f8;
}
/* IMAGES
=============================================================================*/
img {
max-width: 100%
}
</style>
</head>
<body>
<h1>Sketch of Data Structure&Algorithm</h1>
<p>By <a href="mailto:i@jas0n1ee.me">jas0n1ee</a><br />
内容皆为白铂老师课件中节选 </p>
<hr />
<h2>教学内容</h2>
<h3>△基本概念</h3>
<pre><code>数据处理
数学模型
算法分析
</code></pre>
<h3>△非数值问题</h3>
<pre><code>数据结构
线性表
栈
队列
树
图
非数值算法
查找
排序
</code></pre>
<h3>△数值问题</h3>
<pre><code>误差分析
线性方程组
非线性方程
拟合与插值
最优化初步
</code></pre>
<h3>△算法设计</h3>
<pre><code>蛮力☺、贪心
分治、减治
搜索算法
动态规划☆
算法优化
随机算法
计算复杂性
</code></pre>
<hr />
<h1>△基本概念</h1>
<p><strong>数据是客观世界的描述&&算法是处理数据的工具</strong></p>
<h2>数据！</h2>
<p>数据是用有意义的符号对客观对象进行地逻辑归纳与描述<br />
数据是反映客观对象属性的数值<br />
数据是表达知识的字符的集合 <br />
数据是构成信息和知识的原始材料</p>
<h2>算法？</h2>
<h3><code>算法是问题的程序化解决方案</code></h3>
<p>算法强调的是精确定义的求解过程，而不是问题的答案<br />
<strong>五个特征</strong> </p>
<pre><code>有穷性：算法必须在有限步后结束，且每步必须在有限时间内完成
确定性：算法的描述必须无歧义，执行结果是确定的且精确地符合要求或期望
可行性：算法都可通过已实现的基本操作运算的有限次执行来实现
输入：算法有零个或多个输入，这些输入取自某个特定的对象集合
输出：算法有一个或多个输出，输出量是算法计算的结果
</code></pre>
<p><strong>好算法的四个标准</strong> </p>
<pre><code>正确性
可读性
健壮性
高效率
</code></pre>
<h3>☆☆☆<strong>时间复杂度的估算方法</strong></h3>
<p>算法的执行时间=Σ操作的执行次数×操作的执行时间<br />
算法操作包括<strong>控制结构</strong>和<strong>原操作</strong><br />
<code>顺序结构</code>，<code>分支结构</code>，<code>循环结构</code><br />
算法的执行时间与<strong>基本操作执行次数</strong>之和成正比</p>
<h3>空间复杂度</h3>
<pre><code>指令空间（Instruction Space）：是用来存储程序指令所需空间
数据空间（Data Space）：存储运行过程中常量和变量所需的空间
环境空间（Environment Space）：系统为程序运行，特别是函数调用提供的空间
</code></pre>
<h2>数学模型与算法</h2>
<p><strong>数据结构是数学模型</strong> </p>
<h3>几种常见的逻辑结构</h3>
<p><img src="./img/3-1.jpg" height=300><br />
<strong>常见的存储结构</strong><br />
顺序存储<br />
链式存储</p>
<h1>△非数值问题</h1>
<h2>数据结构：具有特定组织结构的数据元素的集合(逻辑结构&存储结构)</h2>
<h3>数据元素和数据项</h3>
<p><strong>数据元素</strong>（Data Element）：数据的基本单位<br />
<strong>数据项</strong>（Data Item）：数据结构中讨论的最小单位 </p>
<h2>二元关系和抽象数据类型</h2>
<h3>二元关系 -《数据结构与算法》1.1.2、1.1.3</h3>
<p><strong>定义：设集合M和N的笛卡尔积为M×N，M×N的任意子集R称为M到N的一个二元关系。</strong></p>
<pre><code> 若(a，b)∈R，则称a为R的前件，称b为R的后件
若M= N，则R∈M×M称为M上的二元关系
</code></pre>
<h3>常见二元关系</h3>
<pre><code>=、≤、≥
等价关系
偏序关系
全序关系
逆序关系
</code></pre>
<p>请自行脑补大一上的离散课</p>
<h3>抽象数据类型（ADT）-《数据结构与算法》1.3</h3>
<p>ADT是一个数学模型及定义在该模型上的一组操作<br />
数据抽象：描述的是实体的本质特征、功能及外部用户接口<br />
数据封装：将实体的外部特性和内部实现细节分离，对外部用户隐藏内部实现细节，使得使用和实现分离<br />
<strong>描述方法：</strong> </p>
<pre><code>ADT 抽象数据类型名{
数据对象：〈数据对象的定义〉
数据关系：〈数据关系的定义〉
基本操作：〈基本操作的定义〉
基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉
} ADT 抽象数据类型名
</code></pre>
<p>编者按：ADT不同于伪代码，它更接近于真实的代码，但它的作用并不是编译成程序运行，而是对一个数据类型（结构）做一个代码风格的说明。（至于我说的靠不靠谱你们自己判断吧(╯‵□′)╯︵┻━┻）</p>
<h2>数据的逻辑结构</h2>
<h3>几种常见的逻辑结构</h3>
<p><img src="./img/3-1.jpg" height=300><br />
<strong>常见的存储结构</strong><br />
顺序存储<br />
链式存储</p>
<h2>线性表 -《数据结构与算法》2.1、2.2、3.1、3.3</h2>
<p><strong>线性表是一种有序结构，长度定义为线性表中元素的个数</strong><br />
线性表的合并 </p>
<pre><code>假设有两个线性表La和Lb，要将两个线性表合并，即将所有在线性表Lb中但不在La中数据元素插入到La中
</code></pre>
<p>线性表的保序归并 </p>
<pre><code>已知线性表La和Lb中的元素按值的递增顺序排列，要求将两个线性表归并成为一个新的有序线性表Lc
</code></pre>
<h3>存储</h3>
<p><strong>顺序存储</strong> <br />
插入操作复杂度期望<br />
<img src="./img/3-2.jpg" height=80></p>
<p>删除操作复杂度期望<br />
<img src="./img/3-3.jpg" height=80></p>
<p><strong>单向链表</strong> ☆似乎这个比较重要</p>
<pre><code>数据域：存储数据元素
指针域：指向直接后继结点
</code></pre>
<p>插入删除操作复杂度为 遍历O(n)+操作O(1)<br />
<strong>存在问题：单向链表的插入和删除操作，需单独考虑头结点的情况</strong></p>
<pre><code>解决方法：带表头结点的单向链表
</code></pre>
<p><strong>双向循环链表</strong> 原理同单向链表</p>
<h3>优缺点</h3>
<pre><code>线性表的顺序存储——顺序表
形式：用一组地址连续的存储单元依次存储线性表的数据元素
优点：可随机存取
缺点：插入和删除操作需要移动表中的数据元素；事先确定规模，空间效率不高
线性表的链式存储——链表
形式：用一组任意的存储单元（附加指针）存储表中的数据元素
优点：插入和删除操作无需移动表中的数据元素；无需事先确定规模，空间利用率高
缺点：不能随机存取
</code></pre>
<h2>队列-《数据结构与算法》2.5.1-2.5.3、3.2.2</h2>
<p>队列是限定在表的一端进行插入，而在另一端进行删除的线性结构<br />
<img src="./img/3-4.jpg" height=80> </p>
<p><strong>顺序队列</strong><br />
<img src="./img/3-5.jpg" height=60> <br />
入队：新元素加入rear指示的位置，rear指针进一：<code>rear = rear + 1</code> <br />
出队：取出front指示的元素，front指针进一：<code>front = front + 1</code></p>
<p><strong>循环队列</strong><br />
<img src="./img/3-6.jpg" height=100> <br />
rear指向maxSize-1，入队进到0<br />
front指向maxSize-1，出队进到0<br />
指针操作的求模（求余）实现 </p>
<pre><code>出队: front = (front + 1) mod n
入队: rear =(rear + 1) mod n
</code></pre>
<p><strong>链式队列</strong><br />
<img src="./img/3-7.jpg" height=60> <br />
入队时没有队满的问题<br />
出队时则有<strong>队空的问题</strong> </p>
<h2>栈-《数据结构与算法》2.3、3.2.1、2.4.1、2.4.4</h2>
<p>栈是只允许在一端进行插入和删除操作的线性结构<br />
允许插入和删除操作的一端称
为栈顶（Top），另一端称
为栈底（Bottom）<br />
<img src="./img/3-8.jpg" height=150><br />
插入操作称为入栈（Push）
删除操作称为出栈（Pop）<br />
<strong>顺序栈</strong><br />
<em>时间复杂度</em>:<br />
顺序栈的操作，如进栈和出栈，都是O(1)时间复杂度<br />
<strong>链式栈</strong><br />
<em>时间复杂度:</em><br />
链式栈的基本操作，如进栈和出栈，都是O(1)时间的<br />
链式栈的建立和销毁是O(n)时间的</p>
<h3>应用</h3>
<p>栈的显示应用：括号匹配、表达式求值、进制转换、迷宫求解<br />
栈的隐式应用：函数调用、递归</p>
<h2>递归</h2>
<p>编者按：为什么在这里会提到递归？递归减少了程序的代码量，但却增加了程序的“不稳定因素”。由此引出消除递归的必要，与栈在消除递归中的应用。<br />
<strong>若一个过程直接地或间接地调用自己, 则称这个过程是递归的</strong><br />
斐波那契数列<br />
汉诺塔问题<br />
<img src="./img/3-9.jpg" height=60> </p>
<pre><code>void move(int n, int x, int z, int y)
{
if (n >= 0)
{
move(n-1, x, y, z);
printf(“Move disk %d from %d to %d”, n, x, z);
move(n-1, y, z, x);
}
}
</code></pre>
<p>当n越大时，递归层数越多，系统容易爆栈，因而要消除递归 </p>
<h3>递归的消除</h3>
<p>一部分递归可直接用循环实现其非递归过程<br />
一部分递归可用递推实现其非递归过程<br />
很多情形必须借助显式的栈来实现非递归过程</p>
<h2>串-《数据结构与算法》6.8</h2>
<p>有限长度的字符序列，即限定数据元素为字符的线性表<br />
两个串相等当且仅当 </p>
<pre><code>两个串的长度相等
每个对应位置的字符相同
</code></pre>
<h3>串匹配</h3>
<pre><code>已知目标串T 和模式串P，模式匹配就是要在目标串T 中找到一个与模式串P 相等的子串
</code></pre>
<p><strong>Brute-Force 布鲁特福斯算法</strong> </p>
<pre><code>最坏情况下的时间复杂度为O(n×m)
</code></pre>
<p><strong>KMP 算法</strong> ☆一定要好好看啊╮(╯▽╰)╭<br />
当模式P 不匹配时，尽量向右移动最大距离，避免重复<br />
<em>预处理函数Next</em> </p>
<pre><code>void Next(char *P)
{
int m = strlen(P); // 模式串P 的长度
N[0] = 0; // 位置0 处的部分匹配串长度为0
int i = 1; j = 0; // 初始化比较位置
while(i < m)
{
if(P[i] == P[j]) // 已经匹配了j+1 个字符
{
N[i] = j+1; // 部分匹配串长度加1
i++; j++; // 比较位置各加1
}
else if( j > 0) j = N[j-1]; // 移动：用部分匹配串对齐
else f N[i++] = 0;g //j 在串头时部分匹配串长度为0
}
}
</code></pre>
<p>KMP 算法的时间复杂度为O(m + n)<br />
<strong>Boyer-Moore 算法</strong><br />
将模式串P 与主串T 的子序列进行反向比较<br />
若P 包含c，则移动P 使c 在P 中的最后一次出现P[l] 对准T[i]<br />
否则，移动P 使P[0] 对准T[i+1]<br />
最坏情况下，算法的时间复杂度为O(n × m + s) </p>
<h2>树</h2>
<p>树是由n≥0 个结点组成的集合，有一个根（Root）结点，它只有直接后继，无直接前驱<br />
除根以外的其它结点划分为m > 0 个不相交的有限集合，每个集合又是一棵树，并称之为根的子树<br />
<img src="./img/4-1.jpg" height=200> </p>
<h4>与树相关的概念较多，在此不赘述，但请认真了解</h4>
<h3>二叉树</h3>
<p>二叉树是k = 2 的k 叉树<br />
二叉树有五种不同形态<br />
<img src="./img/4-2.jpg" height=50><br />
具有n 个结点的完全二叉树的深度为log2 (n + 1)<br />
完全二叉树不一定是满的！<br />
<strong>二叉树的链式存储</strong> </p>
<pre><code>数据域：存放数据
指针域：存放指向左子树和右子树的指针
typedef struct tnode
{
ElemType data;
struct tnode *lchild;
struct tnode *rchild;
} TreeNode;
</code></pre>
<p><strong>二叉树遍历</strong>——访问根结点的时机选择<br />
先序遍历：V - L - R<br />
中序遍历：L - V - R<br />
后序遍历：L - R - V<br />
<strong>以上三种用递归来实现</strong><br />
层序遍历 用队列来实现<br />
<strong>二叉树的建立</strong><br />
由二叉树的先序序列和中序序列可唯一地确定一棵二叉树 </p>
<h3>Huffman 树与编码</h3>
<p>树的路径长度：从树根到所有叶子结点的路径长度之和<br />
在所有路径相同的二叉树中带权路径长度最小的树称为Huffman树或最优二叉树<br />
<strong>构造</strong> 参考离散（贪心算法） <br />
<strong>Huffman 编码</strong><br />
平均编码长度最短
满足前缀编码的性质（任一字符编码都不是其它字符编码的前缀）<br />
<strong>二叉搜索树</strong><br />
在二叉搜索树上可以高效地进行查找</p>
<h2>图</h2>
<p>图定义为G = (V,E)<br />
V 是一个有限集合<br />
E 是V 中元素的有序（或无序）二元组，即{<v,w> |v,w ∈ V; v ≠w}</p>
<p>某些图的边具有与它相关的数, 称为权，这种带权的图叫做网络<br />
<img src="./img/4-3.jpg" height=200> </p>
<pre><code>路径长度是路径上边的数目
路径序列中没有重复出现的顶点称为简单路径
路径的起点和终点相同（v = v*）称为回路或环
除了v 之外，其余顶点不重复出现的回路称为简单回路
</code></pre>
<p><strong>无向图</strong><br />
在无向图中，如果从顶点v 到顶点w 有路径，则称v 和w 是连通的<br />
对于图中任意两个顶点v都是连通的，则称G 是连通图
无向图的极大连通子图称为连通分量<br />
<strong>有向图</strong><br />
在有向图中，如果对于每一对vi，vj ，从vi 到vj 和从vj 到vi 都存在路径，则称G 为强连通图<br />
有向图的极大强连通子图称为有向图的强连通分量</p>
<p><strong>欧拉路径</strong>是遍历图中每条边且只访问一次的路径<br />
终点回到起点的欧拉路径是<strong>欧拉回路</strong> </p>
<h3>图的存储</h3>
<p><strong>邻接矩阵表示</strong><br />
图的邻接矩阵表示需要与v^2 成比例的存储空间<br />
网络的邻接矩阵表示：如果将邻接矩阵中元素改为边的权值，邻接矩阵可以用来表示网络 </p>
<pre><code>空间复杂度O(|V|^2)
边插入操作O(1)
边删除操作O(1)
判边存在操作O(1)
图的迭代器
访问某一个顶点的邻接顶点O(|V|)
访问所有顶点的邻接顶点O(|V|^2)
</code></pre>
<p><strong>邻接表表示</strong><br />
采用一个链表数组来表示图<br />
每个链表头结点为图的顶点<br />
同一个顶点发出的边链接在同一个链表中<br />
<img src="./img/4-4.jpg" height=200> </p>
<p>无向图的邻接表表示需要(|V| + 2|E|) 个链表结点<br />
<strong>最坏情况时间复杂度分析</strong> </p>
<pre><code>空间复杂度O(|V| + c|E|)
边插入操作O(1)
边删除操作O(|V|)
判边存在操作O(|V|)
图的迭代器
访问某一个顶点的邻接顶点O(|V|)
访问所有顶点的邻接顶点O(|V|+ |E|)
</code></pre>
<p>对于稠密图，适于采用邻接矩阵表示<br />
对于稀疏图，适于采用邻接表来表示 </p>
<h3>图的遍历</h3>
<p><strong>深度优先搜索</strong><br />
<strong>广度优先搜索</strong> </p>
<h2>最小生成树</h2>
<p>生成树，包含图中全部n 个顶点，但只有n -1 条边<br />
<img src="./img/4-5.jpg" height=300> <br />
<strong>最小生成树</strong>对于给定的加权无向连通图，最小生
成树是一棵生成树，并且其权（所有
边的权值之和）不会大于其它任何生
成树的权
<strong>KRUSKAL 算法</strong> </p>
<pre><code>对图中所有边按权值进行排序
令最小生成树的边集为空
从图中取出权值最小的一条边
如果这条边与最小生成树中的边能构成环，则舍弃
否则，将这条边加入最小生成树
重复上述过程，直至将|V|-1 条边加入最小生成树
</code></pre>
<p>Kruskal 算法的时间复杂度为O(|E| log|E|)<br />
Kruskal 算法对于稀疏图是好的选择</p>
<p><strong>PRIM 算法</strong> </p>
<pre><code>初始最小生成树是一个空集
首先从图G 中任取一个结点a 加入最小生成树，找出当前非最小生成树的顶点与当前最小生成树直接相连的所有边
取出最短边，把它和非最小生成树顶点b 加入最小生成树，更新边序列
重复上述过程，直到最小生成树包括G 中所有结点
</code></pre>
<p>Prim 算法的时间复杂度是O（|V|^2)<br />
对于稠密图，Prim 的邻接矩阵实现是首选方法 </p>
<h3>最短路径</h3>
<p><strong>单源最短路径</strong>：给定一个起始顶点s，找出从s 到图中其它各顶点的最短路径，即最短路径树<br />
<strong>全源最短路径</strong>：找出连接图中各对顶点的最短路径 </p>
<p><strong>Dijkstra 算法</strong> -单源最短路径</p>
<pre><code>初始化点集S = {0}，V 为顶点集
确定各顶点到源点的最短距离
从V\S 中找出距源点s 最近的结点v
更新S，使S = S + {v}
更新各点到源点的距离
重复步骤3，直至S = V
</code></pre>
<p>Dijkstra 算法的时间复杂度为O(|V|^2) </p>
<p><strong>全源最短路径</strong><br />
对图中每个顶点使用Dijkstra 算法<br />
or<br />
<strong>Floyd 算法</strong> </p>
<pre><code>初始化|V|×|V| 的矩阵D0 为图的边值矩阵
对k = 0~n-1进行如下迭代
Dk[i][j] =min{Dk-1[i][j],Dk-1[i][k]+Dk-1[k][j]}
|V|×|V| 即为从顶点i 到顶点j 的最短路径长度，这条路径不经过编号大于k 的顶点
最后得到的就是全源最短路径矩阵
</code></pre>
<p>Floyd 算法可以在与O(|V|^3)的时间内计算出一个网中的所有最短路径<br />
<strong>编者按：这四种算法似乎比较重要，好好看。前三个本质上为贪心，最后一个为动态规划</strong> </p>
<h2>二分图</h2>
<p>(这部分介绍了但算法没细讲，或者我没认真听(╯‵□′)╯︵┻━┻)<br />
二分图是满足如下性质的图：<br />
顶点集合V 分割为两个子
集V1 和V2，且满
足V1∪V2 = V 和V1 \ V2 = ∅;<br />
边集E 中的每条边e 的两个端点必
须在不同的顶点集内<br />
<strong>二分图匹配</strong> <br />
匈牙利算法的复杂度为O（n^4)<br />
<strong>加权二分图的匹配</strong><br />
稳定婚姻问题...</p>
<h1>非数值算法</h1>
<h2>查找</h2>
<p>查找算法的复杂性：关键字/数据规模<br />
查找表（Search Table）是由同一类型数据元素构成的集合<br />
平均查找长度：在查找过程中，为确定目标在查找表中的位置，需要进行关键字比较次数的期望值
ASL =ΣPiCi</p>
<h2>顺序查找与索引查找</h2>
<h4>顺序查找</h4>
<p>(顺序查找过于简单不再叙述)<br />
对顺序表顺序查找<br />
<img src="./img/5-1.jpg" height =70><br />
<strong>折半查找</strong><br />
编者按：折半查找就是二分搜索，是一种优化的顺序表查找算法（我也不知道说的对不对）<br />
折半查找可以用一个二叉树结构来描述<br />
对于一次查找,无论成功还是失败，折半查找需要的比较次数不会超过log2 N </p>
<p><strong>不同表示线性表的查找效率比较</strong><br />
<img src="./img/5-2.jpg" height =100> </p>
<h3>索引查找</h3>
<p>将有n 个结点的线性表划分为m 个子表，分别存储各子表<br />
另设一个有m 个结点（索引项）的索引表，每个结点存子表第一个结点的地址及相关信息<br />
<strong>索引存储方式</strong> </p>
<pre><code>索引表——顺序表或链表
子表——顺序表或链表
</code></pre>
<p>索引表特点：表不大，表中元素不常变动<br />
适合用顺序表来表示索引表<br />
<strong>索引表为顺序表 子表也为顺序表情况</strong><br />
<img src="./img/5-3.jpg" height =150><br />
索引查找比全表顺序查找效率高 </p>
<p><strong>索引表采用顺序表 子表采用链表情况</strong><br />
<img src="./img/5-4.jpg" height =100><br />
优点：<br />
索引表结构简单，便于查找<br />
子表结点插入、删除不需要移动表中元素</p>
<p><strong>多重索引</strong>：当索引表很大时，对索引表再做索引 </p>
<h4>分块查找</h4>
<p>分块查找也称索引顺序查找，是顺序查找的改进<br />
把线性表顺序划分为若干个子表（块）后满足</p>
<pre><code>子表之间递增（或递减）有序，即后一子表的每一项大于前一子表的所有项
块内元素可以无序
</code></pre>
<h3>多关键字索引文件结构</h3>
<p><strong>多重表文件</strong> </p>
<pre><code>次关键字项：经常需要对其查询的数据项（一项或多项）
次关键字：每个记录的次关键字项的值
</code></pre>
<p>多重链表文件结构： </p>
<pre><code>1 主文件为顺序文件
2 对主关键字建立索引表，称为主索引表
3 主文件中对每个次关键字项设一指针域，用以链接相同关键字的记录（单链表）
4 对每个次关键字分别建立索引表，称为辅索引表
</code></pre>
<p><strong>倒排文件</strong><br />
倒排文件也是一种多关键字索引文件结构,适用于多关键字查询,与多重链表文件相同之处：主文件+主索引表+辅索引表<br />
<img src="./img/5-5.jpg" height =50><br />
<img src="./img/5-6.jpg" height =50> </p>
<p>优点：处理多关键字查询时，通过集合运算直接得到结果 </p>
<h2>二叉搜索树</h2>
<p>二叉搜索树（BST：Binary SearchTree）或者是一棵空树，或者是具有下列性质的二叉树： </p>
<pre><code>1 每个结点有一个关键字（Key）
2 任意结点关键字大于等于该结点左子树中所有结点含有的关键字
3 同时该结点的关键字小于等于右子树中所有结点含有的关键字
</code></pre>
<p>二叉搜索树的<strong>插入过程</strong>类似于搜索，在搜索失败后执行插入操作<br />
<img src="./img/5-7.jpg" height =150><br />
性能特性<br />
完美的平衡树是极为罕见的，高度不平衡的树也不多见<br />
<strong>二叉搜索树中的旋转操作</strong><br />
旋转使一棵树中，结点和结点的一个子孙互换角色，但仍然保持结点关键字之间的次序<br />
右旋转（Right Rotation）涉及到结点及其左孩子<br />
左旋转（Right Rotation）涉及到结点及其右孩子<br />
<strong>更多的二叉搜索树</strong> </p>
<pre><code>高度平衡的二叉搜索树——AVL树
实用的比较平衡的二叉搜索树——红黑树
多路平衡的动态查找结构——B-树
</code></pre>
<h2>散列</h2>
<p><strong>散列表</strong>（Hash）是将一组关键字映射到一个有限的、地址连续的区间上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置<br />
散列表的冗余度和冲突是一对矛盾 </p>
<p><strong>散列函数</strong>把关键字映射为存储地址<br />
散列函数应是简单的，能在较短的时间内计算出结果<br />
散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有m 个地址，其值域必须在0 到m - 1 之间<br />
理想的散列函数应近似为随机的，对每一个输入，相应的输出在值域上是等概的 </p>
<h4>三种方法</h4>
<p><strong>数字分析法</strong><br />
仅适用于事先知道表中所有关键码每一位数值的分布情况，完全依赖于关键码集合；若换一个关键码集合，需重新选择<br />
<strong>平方取中法</strong><br />
先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址<br />
<strong>折叠法</strong><br />
把关键码自左到右分成位数相等的几部分，每部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些<br />
把这些部分的数据叠加起来,就可以得到具有该关键码的记录的散列地址</p>
<h4>冲突问题</h4>
<p><strong>链地址法</strong>
两个关键字散列到同一地址，也就是冲突问题<br />
最简单的方法是对每个散列地址建立一个链表，将散列到同一地址的不同关键字存入相应的链表中，这种方法称为<strong>链地址法</strong><br />
<img src="./img/5-8.jpg" height =100> </p>
<p><strong>开放地址法</strong><br />
对表长M 大于元素数目N 的情况，依靠空的存储空间来解决冲突问题，这类方法被称为<strong>开放地址法</strong><br />
N 为元素数目，M 为表长，定义负载因子α= N/M<br />
<strong>散列表的查找</strong><br />
查找过程和建表过程一致
假设采用开放定址处理冲突，对于给定值k，计算散列地址
i = Hash (k)</p>
<p><strong>散列表的删除</strong><br />
<em>在开放定址散列表中，直接对元素进行删除是不行的</em></p>
<p><strong>双重散列</strong><br />
双重散列不是检查冲突点后面每一个表位置，而是采用第二个散列函数得到一个固定增量序列用于探测序列</p>
<h2>排序-《数据结构与算法》7.1、7.2</h2>
<p>排序的时间开销是衡量算法好坏的最重要的标志<br />
算法执行时所需的附加存储：评价算法好坏的另一标准 </p>
<h3>冒泡排序</h3>
<p>（过于简单不做赘述）
最坏情况：
<img src="./img/5-9.jpg" height =50> </p>
<h3>插入排序</h3>
<p>直接插入<br />
折半插入<br />
希尔（Shell）排序 </p>
<p><strong>直接插入</strong><br />
平均情况下，直接插入排序约需要n^2/4 次比较操作和半交换操作<br />
<strong>折半插入</strong><br />
插入排序算法中，在插入第k 个元素时，前k-1 个元素组成的序列已经是有序的，可以利用折半查找法寻找的第k-1 个插入位置<br />
长度为k 的序列，折半查找需要经过log2 k+ 1 次比较<br />
n 个对象用折半插入排序需要进行的比较次数约为nlog2n<br />
<strong>总的时间复杂度仍然是O（n^2）</strong><br />
<strong>希尔排序</strong><br />
编者按：就是有步长的排序。。我是这么觉得的..<br />
好的步长序列：1; 8; 23; 77; 281; 1073 hi=4^(i+1) +3×2^i+1 </p>
<h3>快速排序 -《数据结构与算法》7.3</h3>
<pre><code>将待排序序列a 划分为两个部分，满足下述条件
a [i] 位于它在序列中的正确位置
前面的元素a [l] ~ a [i-1] 都比a [i] 小
后面的元素a [i + 1] ~a [h] 都比a [i] 大
然后分别对两个部分进行划分
每次划分都至少将一个元素放在它最终应该位于的正确位置，直至所有元素都排序完成
</code></pre>
<p>其中的<strong>划分操作</strong> </p>
<pre><code>l 和r 为序列的第一个和最后一个元素，v 表示划分元素的值，i 表示左侧指针，j 表示右侧指针
选择a [r] 作为划分元素—，划分后位于正确位置
从序列的最左边向中间扫描，找到一个比划分元素大的元素
从序列的最右边向中间扫描，找到一个比划分元素小的元素
交换这两个元素
当扫描指针i 和j 相遇时，和划分元素交换，划分完成
</code></pre>
<p>性能分析：最好情况时间复杂度为O(N log2N)<br />
But<br />
快速排序平均情况下需要lgN 的递归栈，但在最坏情况下可以达到N</p>
<h3>归并排序 -《数据结构与算法》7.4</h3>
<p>归并是将两个或两个以上的有序表合并成一个新的有序表<br />
，二路归并时间复杂度为O(N)
<strong>自底向上的归并排序</strong><br />
自底向上归并排序对整个文件进行m-m 的归并操作，每次m 的值都变成两倍<br />
自底向上归并排序中，每一步进行归并排序的子序列的大小是2 的幂数，最后一个子序列的大小是一个例外<br />
时间复杂度为O(N log2 N)</p>
<p><strong>自顶向下的归并排序</strong><br />
可用递归实现，原理相同不再赘述。</p>
<hr />
<p><img src="./img/5-10.jpg" height =200> </p>
<pre><code>基本排序方法在平均情况下的时间复杂度是O（N^2）
高级排序方法在平均情况下的时间复杂度是O(N logN)
就平均性能来说，快速排序比归并排序好
归并排序是稳定的，快速排序是不稳定的，性能可能退化
</code></pre>
<p>可以参考B站上的热门视频<a href="http://bilibili.kankanews.com/video/av685670/">15种排序</a></p>
<h1>△数值问题</h1>
<p>《科学计算导论》1.1、1.2、1.3.1-1.3.9&《数值方法与计算机实现》1.1、1.2<br />
数值分析/科学计算 </p>
<pre><code>设计和分析数值型的算法，用于解决科学和工程领域的数学问题
</code></pre>
<h4>数值分析研究问题</h4>
<pre><code>线性方程组
非线性方程
最优化问题
拟合与插值
</code></pre>
<p><strong>解的特性</strong> 存在性、唯一性、最优性、精确性<br />
<strong>算法的特性</strong> 性能和效率 </p>
<h4>适定性</h4>
<pre><code>解存在
解是唯一的
连续地依赖于问题数据
</code></pre>
<p>不满足条件的问题，被称为不适定的</p>
<h4>病态性</h4>
<pre><code>解可能对于输入数据很敏感
</code></pre>
<p>病态是问题的特性，与所选择的算法没有关系 </p>
<h2>误差分析</h2>
<h3>绝对误差&相对误差</h3>
<pre><code>绝对误差= 近似值- 真值
相对误差= 绝对误差/ 真值
近似值= 真值×(1 + 相对误差)
相对误差≈ 估计误差/ 近似值
</code></pre>
<h3>误差来源</h3>
<p><img src="./img/6-1.jpg" height=200></p>
<pre><code>误差= 计算误差+ 数据传播误差
计算误差= 截断误差+ 舍入误差
</code></pre>
<h3>舍入误差</h3>
<p>计算机采用的浮点数是实数轴上不等距有限点集<br />
因此，在计算机的浮点数系上, 四则运算实际上是不封闭的 </p>
<h3>前向误差与后向误差</h3>
<p>前向误差（Forward Error）<img src="./img/6-2.jpg" height=30><br />
后向误差（Backward Error）<img src="./img/6-3.jpg" height=25><br />
<img src="./img/6-4.jpg" height=200> </p>
<h3>敏感性和病态性</h3>
<p><strong>条件数</strong>表示从输入数据的相对差异到解的相对差异的放大系数<br />
<img src="./img/6-5.jpg" height=50> </p>
<p>cond ≤ 1 表明问题是不敏感的，是良态的<br />
cond >> 1 表明问题是敏感的，是病态的<br />
实际过程中由于难以求得条件数，往往只能满足于在输入数据的定
义域上得到条件数的估计值，或者得到其上限
<strong>绝对条件数</strong> </p>
<p><img src="./img/6-6.jpg" height=50> </p>
<p>函数求值和方程求解问题的敏感性是相反的</p>
<h3>浮点数系统</h3>
<p>数据x 按照浮点数表示为<br />
<img src="./img/6-7.jpg" height=70><br />
除非所表示的数为0，否则尾数的首位d0 不为0；满足这个条件的浮点数系统成为正规化的<br />
最小的正的正规化浮点数为UFL =β^L，称为下溢限<br />
最大的正的正规化浮点数为OFL = β^(U+1) (1-β^-p)，称为上溢限<br />
在指数域达到最小值时，允许尾数首位为0，称为次正规化</p>
<h4>舍入误差</h4>
<p>截断：将x 的β基底展开的第p-1 位后之后截去，也称向零舍入法<br />
最近舍入：取与x 最接近的浮点数，在相等情况取最后一个为偶数</p>
<h4>有效数字</h4>
<p><img src="./img/6-7.jpg" height=60><br />
<img src="./img/6-8.jpg" height=50> </p>
<h4>相对误差</h4>
<p>有n 位有效数字的相对误差<br />
<img src="./img/6-9.jpg" height=50> </p>
<h3>溢出</h3>
<p>浮点运算还可能导致溢出，下溢可以用0 来表示，而上溢是致命的<br />
<em>大数吃小数</em><br />
<em>抵消</em> 两个相近的数相减会造成有效数字的损失</p>
<hr />
<pre><code>在计算过程中，误差的存在和产生是不可避免的
稳定的算法，使得误差在传播过程中是衰减的或者可控的
对于良态的问题，利用稳定的算法就可以得到满足精度要求的解
对于误差来源的分析和理解，有助于我们设计出稳定的算法
</code></pre>
<h2>线性方程组</h2>
<p>矩阵、线性方程组的特性、范数不再赘述，请参考线性代数 或《科学计算导论》2.1、2.2、2.3<br />
<img src="./img/7-2.jpg" height=150> <br />
<strong>矩阵的条件数</strong><br />
<img src="./img/7-1.jpg" height=50><br />
矩阵的条件数刻画了矩阵对于非零矢量最大的伸展和压缩能力<br />
矩阵的条件数越大，说明矩阵越接近奇异 </p>
<p><strong>直接解法</strong> -《科学计算导论》2.4.1-2.4.8、2.5.1《数值方法与计算机实现》2.1、2.5.1、2.5.2</p>
<pre><code>高斯消去法
LU 分解法
Gauss—Jordan
Cholesky
</code></pre>
<p>由于这部分知识在线性代数中已经学过，就不再过多介绍。<br />
注意：
在高斯消元中，对角线上的元素aii会作为除数，如果aii很小或者为0则需要重新选取主元。 </p>
<p><strong>线性方程组解的精度</strong> -《科学计算导论》11.5.1-11.5.3《数值方法与计算机实现》2.3
残差向量<strong>r</strong> = <strong>b</strong> -<strong>Ax</strong><br />
当A 为良态时，小的相对残差意味着解的相对误差也小<br />