少女Q的量化交易转型之路 #week 1 之二
Continued…
第二章 算法
算法的定义：算法是解决特性问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。
算法的特性：有穷性，确定性，可行性，输入，输出。
算法设计要求：正确性，可读性，健壮性（对于输入数据不合格的情况做合适的处理），高效率和低存储量需求。
2.1 算法效率的度量方法
事后统计方法：用测试好的程序进行多次测试，耗时耗力，不推荐。
事前分析估算方法：对于一个函数，步骤越少，肯定编译的时间就越少。每一条指令算一个时间增加区间。所以可以提前知道函数大概需要耗费的程度。如下
第一种算法：
int 1, sum = 0, n = 100; /* 执行1次*/
for (i - 1; i <= n; i++) /*执行n+1次*/
{
sum = sum + i; /*执行n次*/
}
printf("%d", sum); /*执行1次*/
第二种算法：
int sum = 0, n = 100; /*执行一次*/
sum = (1 + n) * n/2; /*执行一次*/
printf("%d",sum); /*执行一次*/
第一种算法执行了2n+3次，第二种执行了3次。但不是每次算法都是要遍历计算出来的，很多算法效率可以抽象成一个函数出来。
2.2 函数的渐进增长
一种算法2n+3次运算，另一种3n+1次运算。可见在n=2时，是判定两个算法好坏的转折点。
给出定义：输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总大于另一个函数，称函数是渐进增长的。并且当函数为高阶时，一些低阶参数以及常数项可以忽略。
2.3 算法时间复杂度
算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法渐进时间复杂度，简称时间复杂度。用大写O()来体现算法的时间复杂度的记法，称之为大O记法。
推导大O阶：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
得到的结果就是大O阶。
2.3.1 常数阶
int sum = 0, n = 100; /*执行一次*/
sum = (1 + n) *n/2; /*执行一次*/
printf("%d",sum); /*执行一次*/
根据大O阶，第一步把项数3改成1。运行次数函数f(n)=3,时间复杂度为O(1)。
int sum = 0, n = 100;
sum = (1 + n ) *n/2; /*第1次执行*/
sum = (1 + n ) *n/2; /*第2次执行*/
sum = (1 + n ) *n/2; /*第3次执行*/
sum = (1 + n ) *n/2; /*第4次执行*/
sum = (1 + n ) *n/2; /*第5次执行*/
sum = (1 + n ) *n/2; /*第6次执行*/
sum = (1 + n ) *n/2; /*第7次执行*/
sum = (1 + n ) *n/2; /*第8次执行*/
sum = (1 + n ) *n/2; /*第9次执行*/
sum = (1 + n ) *n/2; /*第10次执行*/
printf("%d", sum); /*执行1次*/
事实上无论n为多少，上面两段代码就是3次和12次执行的差异。这种与问题大小无关(n的多少)，执行时间恒定的算法，称为具有O(1)的时间复杂度，又叫常数项。
2.3.2 线性阶
int i;
for (i = 0; i < n; i++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
时间复杂度为O(n)。
2.3.3 对数阶
int count = 1;
while (count < n)
{
count = count * 2;
/*时间复杂度为O(1)的程序步骤序列*/
}
由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由得到。所以这个循环的时间复杂度为O(logn)。
2.3.4 平方阶
循环的时间复杂度等于循环体的复杂度乘以该循环的运行次数。
int i, j;
for(i = 0; i < n; i++)
{
for(j = i; j < n; j++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
当i=0时，内循环执行了n次, 当i=1时，执行了n-1次，…i=n-1时，执行了一次。所以总执行次数为：
用推导大O阶的方法，第一条，没有加法常数可以不考虑;第二条，只保留最高阶项，因此保留;第三条，去除这个项相乘的常数，也就是去除1/2,最终这段代码的复杂度为。
第三章 线性表
3.1 线性表定义
零个或者多个数据元素的有限序列。
3.2 线性表的抽象数据类型
一些c语言里的一些关于线性表的基本操作，之后复杂的操作都是由这些简单的组成。
ADT (List)
Data
线性表的数据对象集合为{ai,a2,....,an}，每个元素的类型均为 DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前去元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。
Operation
InitList(*L): 初始化操作，建立一个空的线性表L。
ListEmpty(L): 若线性表为空，返回true，否则返回false。
ClearList(*L): 将线性表清空。
GetElem(L,i,*e): 将线性表L中的第i个位置元素值返回给e。
LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
ListInsert(*L,i,e): 在线性表L中的第i个位置插入新元素e。
ListDelete(*L,i,*e): 删除线性表L中第i个位置元素，并用e返回其值。
ListLengh(L): 返回线性表L的元素个数。
endADT
3.3 线性表的顺序存储结构
线性表的顺序存储结构，指的是一段地址连续的存储单元依次存储线性表的数据元素。
3.3.1 顺序存储方式
内存中找了块地，通过占位的形式，把一定内存空间占了，然后把相同数据类型的数据元素依次存放在这块空地中。线性表里的每一个数据元素类型都相同，所以可以用一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻元素存储在数组中相邻的位置。
顺序存储三个属性：
存储空间的起始位置：数组Data，它的存储位置就是存储空间的存储位置.
线性表的最大存储容量：数组长度Maxsize.
线性表的当前长度：Length.（Length不能比Maxsize大，因为线性表里头不一定会填满，随着插入和删除的操作，这个量是变化的，所以肯定不会超过存储容量）
地址计算方法：
我们数数都会从1开始，可是很多语言的数组是从0开始。
顺序存储结构的插入与删除：
插入操作：
Target：将元素插到位置i
算法思路：
1.如果插入位置不合理，抛出异常error (Eg 插到线性表长度后头)。
2.如果线性表长度大于数组长度，则error或动态增加容量。
3.从最后一个元素向前遍历到第i个位置，分别将它们都向后移一个位置。
4.将元素插到位置i处
5.表长加1
Attention:注意下标和位数的关系。
删除操作：
Target：删除第i个数据元素
算法思路：
1.删除位置不合理，error（删除length之外的）。
2.从删除元素开始遍历到最后一个元素位置，分别将它们都向前移动一步。
3.表长减一。
3.4 线性表的链式存储结构
对于前面的顺序存储结构，可以说是简单易懂，但是对于电脑来说操作太多是一种耗费。所以为了解决每移动一个元素，后面全体都要移动的劣势。干脆就不用固定位置了。线性表链式存储结构特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以不连续，数据元素可以存在内存任何地方。
头指针指链表的指针，整个链表的存取就从头指针开始进行了，可以说是有标识作用了，经常用头指针冠以链表的名字。
最后一个结点，意味着直接后继不存在了，指针为“空”,null。
为了方便对链表进行操作（在第一元素结点前插入结点和删除第一结点），在单链表的第一个结点前附设一个结点，头结点，头结点数据域可以不存储任何信息。这时头指针指的就是头结点了。（书上头指针图不对）
线性表链式存储结构代码描述：
假设p是指向线性表第i个元素的指针，则该结点ai的数据域用p->data来表示，指针域用p->next来表示。P->next->data = ai+1。
单链表的插入与删除：
单链表的插入：
三个元素的例子：假设存储元素e结点为s，要将s插入到ai和ai+1中。不需要动别的结点，只需要让s->next, p->next俩指针变化。
s->next = p->next; p->next=s;
意思你让p的指针指向s, s的指针指向后面一个。记住顺序不能乱，先把p的指针赋值给s指针，不然会被覆盖掉。
实现代码：
Malloc函数作用是生成一个新的结点，类型与node一样，用来存放e.
单链表的删除：
还是三个元素的例子，ai的结点为q，将它删除，只需要让它前结点的指针指向后面结点即可。
q=p->next; p->next=q->next;
实现代码：free函数，作用让系统回收一个node
3.5 单链表结构和顺序存储结构的一些优缺点
存储上：顺序结构会占用一段连续的存储单元一次存储线性表的数据元素。单链表采用链式存储，是用任意一组的存储单元存放线性表的元素。
时间消耗：顺序结构在查找的时间复杂度为O(1)，单链表为O(n)。
插入删除操作顺序结构O(n)（移动一个后面都要移动），单链表O(1)。
空间性能：顺序结构要预分配空间，分大浪费，小了上溢。单链表则不需要分配存储空间，个数也不受限制。
若是频繁查找，很少进行插入删除操作：顺序存储结构。
若频繁插入删除：单链表结构。
3.6 静态链表
让数组的元素都是由两个数据域组成，data和cur。每个下标都对应一个data（存放数据元素），cur（相当于单链表的指针）。对数组第一个和最后一个元素作为特殊元素处理，不存数据。(图错了，最后cur是1)
举一个甲乙丙丁排列的例子：
此时“甲“这里就存有下一元素“乙“的游标2，“乙“则存有下一元素“丁“的下标3。而“庚“是最后一个有值元素，所以它的cur设置为0。而最后一个元素的cur则因“甲“是第一有值元素而存有它的下标为1。而第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存有7。
插入删除操作：
插入操作：结点申请实现[Malloc()]
很有意思的是，第一句话返回了一个空闲空间的下标值，对应上图就是7。如果返回的空闲下标为真，就把下一个空闲下标拿出来放到space[0].cur备用了。
这段和单链表是一样的思路：
4. k=999(求最后一个下标，好得到第一个有值元素的下标)
5,6. 判断第i个元素是否合理。
7. 上面定义过的函数，可以获得来用的空闲下标j。
10. 将要插入的值e赋给L[j]。
11,12. 用循环得以找到i元素之前那个元素的下标k，不停的迭代cur.
13,14. 将i-1元素的cur赋给L[j],将j的下标赋给L[k]. 完成插队. (不知道这么简单的操作为啥可以说的这么复杂，但是也找不到更好的说法)
删除操作：结点释放的申请[Free()]
把第一个元素的cur(空闲位置的cur)赋值给要删除的元素k的cur，然后把k的下标赋值给第一个元素的cur。
比如把甲删了：
删除操作：