考研《数据规划》常识点总结(1)——序文

从今日初步，我会为我们总结一下考研中，数据规划每章的考点总结，假定有考研的网友，期望可认为你们带来协助，没有考研的，也期望可认为我们在数据规划方面有一些协助，我们多多点赞撑持。
考点
1.1 数据规划的根柢概念；
1.2 笼统数据类型；
1.3 算法和算法的时刻凌乱度。
1.1 数据规划的根柢概念；数据元是数据的根柢单位，一个数据元素可由若干个数据项结束，数据项是构成数据元素的不可以切割的最小单位。例如，学生记载就是一个数据元素，它由学号、名字、性别等数据项构成。
数据目标是具有相同性质的数据元素的集结，是数据的一个子集。
数据类型是一个值的集结和界说在此集结上一组操作的总称。
· 原子类型：其值不可以再分的数据类型· 规划类型：其值可以再分化为若干成分（分量）的数据类型· 笼统数据类型：笼统数据组织和与之有关的操作1.2 笼统数据类型；笼统数据类型（adt）是指一个数学模型以及界说在该模型上的一组操作。笼统数据类型的界说仅取决于它的一组逻辑特性，而与其在核算机内部如何标明和完成无关。一般用（数据目标、数据联络、根柢操作集）这样的三元组来标明。
数据规划的三要素：
1. 逻辑规划是指数据元素之间的逻辑联络，即从逻辑联络上描绘数据，独立于核算机。分为线性规划和非线性规划，线性表、栈、行列归于线性规划，树、图、集结归于非线性规划。
2. 存储规划是指数据规划在核算机中的标明（又称映像），也称物理规划，包括数据元素的标明和联络的标明，依靠于核算机言语，分为次序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、添加、删去快）。
数据的运算：包括运算的界说和完成。运算的界说是关于逻辑规划的，指出运算的功用；运算的完成是关于存储规划的，指出运算的具体操作进程。
1.3 算法和算法的时刻凌乱度。要清楚一点：时刻凌乱度并不是直接对时刻进行核算，而是经过核算算法中的根柢操作的实施次数，来旁边面临运转时刻进行预算。
核算办法：

找到一个根柢操作（最深层循环）分析该根柢操作的实施次数x和疑问规划n的联络x=f(n)x的数量级o(x)就是算法时刻凌乱度t(n)

常用技巧：

加法规则：o(f(n))+o(g(n))=o(max(f(n),g(n)))乘法规则：o(f(n))*o(g(n))=o(f(n)*g(n))o(1)<o(log2n)<o(n)<o(nlog2n)<o(n2)<o(n3)<o(2n)<o(2!)<o(nn)，即常数<对数<线性<幂函数<指数函数

三种凌乱度：

最坏时刻凌乱度：思考输入数据最坏的情况。均匀时刻凌乱度：思考一切输入数据都等概率的情况最佳时刻凌乱度：思考输入数据最佳的情况

例题1：
x = 90; y = 100;
while(y > 0){
if(x > 100){
x = x - 10;
y--;
}else{
x++;
}
}解：运转程序，有 x < 100, x = 91 …… x = 101时，有 x = 91, y = 99，每循环11次y的值减1，所以总循环次数有11 * 100 = 1100。
所以，时刻凌乱度：o(1) ，因为程序的实施次数为常数阶。
例题2：
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
a[i][j] = 0;解：语句 a[i][j] = 0; 实施次数有

可推出实施次数为 m * n 次，所以时

刻凌乱度为 o(m*n)。
例题3：
s = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
s += b[i][j];
sum = s;解：语句 s += b[i][j]; 的实施次数为 n * n 。所以，时刻凌乱度为o(n^2)。
例题4：
i = 1;
while(i <= n)
i = i*3;

/* //推导可知：
i = 1;
while(i <= n)
i = i*2;
//时刻凌乱度为o(logn)，底数为2。
*/解： i 的值为：1，3，9， 27，…用 i(x) 标明第 x 次循环时i的值，则i(x)=3^x, x初始值为0。
语句 i = i*3; 的实施次数为3^x<=n，有x<=log3n（3为底），所以，时刻凌乱度为o(log3n)。
例题5：
x = 2;
while(x < n/2)
x = x * 2;
解：x 的取值是首项为4，公比为2的等比数列，设实施次数为 t，则有2^(t+1)<n/2，即t<log2n/2，即t<log2n/2-1，所以，时刻凌乱度为o(log2n)。
例题6：
x = 0;
for(i = 1; i < n; i++)
for (j = 1; j <= n-i; j++)
x++;解： 解： 语句x++; 的实施次数为

所以，时刻凌乱度为o(n^2)。
例题7：
x = 0;
for(k = 1; k <= n; k*=2)
for (j = 1; j <= n; j++)
x++;
解：此题不一样于（6）小题，内层循环条件 j <= n 与外层循环变量无关。
每实施一次 j 自增一，每次内层循环都实施 n 次，所以内层的时刻凌乱度为 o(n)。
关于外层，设循环次数 t 满足k=2^t<=n ， 所以t<=log2n。
所以，内层的时刻凌乱度*外层的时刻凌乱度即为o(n)*o(log2n)=o(nlog2n)。
所以，时刻凌乱度为 o(nlog2n)。
例题8：
int fact(int n){
if(n <= 1)
return 1;
return n*fact(n-1);
}解：本题是求 n 的阶乘，即 n(n-1)(n-2)*…*2*1，每次递归调用时 fact() 的参数减一，递归出口为 fact(1)，一共实施 n 次递归调用 fact()，所以，时刻凌乱度为 o(n) 。
例题9：
//（9）
x = n; //n>1
y = 0;
while(x ≥ (y+1) * (y+1))
y++;
解：语句 y++; 的实施次数为 n>=(y+1) * (y+1)，有 y<=n^1/2-1，所以，时刻凌乱度为o(n^1/2)。
例题10：
int func(int n){
int i = 0, sum = 0;
while(sum < n)
sum += ++i;
return i;
}
解：i 与 sum 的取值改变如下：

i
sum
1
0+1
2
0+1+2
3
0+1+3
…
…
ｔ

所以，有

所以，时刻凌乱度为o(n^1/2)。
例题11：
for(int i= n-1; i > 1; i--)
for (int j = 1; j < i; j++)
if(a[j] > a[j+1])
a[j]与a[j+1]对换;解：最终一行语句频度在最坏情况下是o(n^2)。
当一切相邻元素都为逆序时，则最终一行的语句每次都会实施。则有

所以，时刻凌乱度为o(n^2)。
例题12：
已知两个长度别离为 m 和 n 的升序链表，若将它们兼并为长度为 m + n 的一个降序链表，则最坏情况下的时刻凌乱度是 o(max(m,n))。
解：两个升序链表兼并，两两比照表中元素，每比照一次，断定一个元素的联接方位（取较小元素）。当一个链表比照结束后，将另一个链表的剩下元素刺进即可。
最坏的情况是两个链表中的元素顺次进行比照，因为2 max(m,n) >= m + n，所以时刻凌乱度为o(max(m,n))。
今日第一章就给我们共享到这儿，期望给我们一些协助，也期望我们多多点赞撑持。