当前位置: 首页 > >

数据结构绪论篇

发布时间:

数据结构三要素(了解)
逻辑机构
存储结构

    若采用顺序存储,则各个数据元素在物理上必须是连续的:若采用非顺序存储,则各个数据元素在物理上可以使离散的数据的存储结构影响存储空间分配的方便程度 Eg:有人想插队数据的存储结构会影响对数据运算的速度 Eg:想找第三个人

数据的运算
数据类型、抽象数据类型(了解)
数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。


1)原子类型。其值不可再分的数据类型。


2)结构类型。其值可以再分解为若干成分(分量)的数据类型。



抽象数据类型(ADT)

抽象数据类型是抽象数据组织及与之相关的操作。




算法效率的度量
算法时间复杂度

事前预估算法时间开销T(n)与问题规模n的关系??T表示Time


#include

void LoveYou(int n);

int main(void)
{
LoveYou(3000);
}
/* 算法1??逐步递增型*/
void LoveYou(int n) //n为问题规模
{
int i = 1; //爱你的程度
while (i<=n) {
i++;
printf("I love You %d
", i);
}
printf("I love You More Than %d
", n);
}



语句频度


12 ?? 1次


13 ??3001次


14/15 ??3000次


17 ?? 1次


T(3000) = 1 + 3001 + 2*3000 +1


T(n) = 3n +3≈3n



当问题规模n足够大时,n保留表达式最高阶即可


T1(n)=3n+3 T1(n)=O(n)


T2(n)=n2+3n+1000 ?简化?> T2(n)=O(n2)


T3(n)=n3+n2+999 T3(n)=O(n3)


大O表示“同阶”,同等数量级。即:当n?>








infty


∞时,二者之比为常数


加法规则
T(n)=T1(n))+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

多项相加,只保留最高阶的项,且系数变为1


乘法规则
T(n)=T1(n) * T2(n)= O(f(n)) * O(g(n)) = O(f(n)* g(n))

多项相乘都保留


Eg:T3(n)=n3+n2




l


o



g


2




log_2


log2?n=O(n3)+O(n2




l


o



g


2




log_2


log2?n)



故T3(n)=n3



? 常对幂指阶


结论??算法1
    顺序执行的代码只会影响常数项,可以忽略只需挑选循环中的一个基本操作分析它的执行次数与n的关系即可如果有多层嵌套循环,只需关注最深层循环循环了几次??Eg:算法2

算法2:

void LoveYou(int n)
{
int i=1;
while (i<=n) {
i++;
printf("I Love YOU %d
", i);
for (int j=1; j<=n; j++) { //嵌套两层循环
printf("I am Iron Man
"); //内层循环执行n?次
}
}
printf("I Love You More Than %d
", n);
}

T(n)=O(n)+O(n2)=O(n2)


算法3??指数递增型

void LoveYou(int n) //n为问题规模
{
int i = 1; //爱你的程度
while (i<=n) {
i=i*2;
printf("I love You %d
", i);
}
printf("I love You More Than %d
", n);
}

计算上述算法的时间复杂度 T(n):


设最深层循环的语句频度(总共循环的次数)为 x,则


由循环条件可知,循环结束时刚好满足 2x > n


x = log2n + 1


T(n) = O(x) = O(log2n)


算法4??搜索数字型

void LoveYou(int flag[], int n)
{
printf("I Am Iron Man
");
for(int i=0; i
if(flag[i]==n) {
printf("I Love You %d
", n);
break;
}
}
}


计算上述算法的时间复杂度 T(n)


最好情况:元素n在第一个位置 ??最好时间复杂度 T(n)=O(1)


最坏情况:元素n在最后一个位置 ??最坏时间复杂度 T(n)=O(n)


*均情况:假设元素n在任意一个位置的概率相同为





1


n




frac{ 1}{n }


n1???*均时间复杂度 T(n)=O(n)



最坏时间复杂度:最坏情况下算法的时间复杂度


*均时间复杂度:所有输入示例等概率出现的情况下,算法的期望运行时间



算法空间复杂度

    S表示"Space"

    如果算法空间与问题规模无关,即空间复杂度为常数阶,我们称

    算法原地工作??算法所需内存空间为常量

    2.

    3.

    a)加法规则

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))


O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)


? 4.函数递归调用带来的内存开销


S(n) = O(n) ??空间复杂度 = 递归调用的深度(考试重点)**


数组递归了解



? S(n) = O(n2)




友情链接: