C语言强化-1.数据结构概述

与408的关联:1. 逻辑结构和存储结构在选择题中会有涉及。2. 时间复杂度几乎是每一年大题必考内容!

逻辑结构与存储结构

逻辑结构(对人友好)

  1. 集合结构(无关系)
  2. 线性结构(一对一)
  3. 树形结构(一对多)
  4. 图形结构(多对多)

存储结构(对计算机友好)

1. 顺序存储

int Array[6] = {1,2,3,4,5,6};//定义数组并初始化
prinf("%d\n",Array[3]);//随机访问第4个元素

2. 链式存储

typedef struct Lnode{
	ElemType data;
	struct Lnode *next;
}Lnode,*LinkList;
Lnode *L;
L = (LinkList)malloc(sizeof(Lnode));
A -> next = B;
B -> next = C;

顺序存储与链式存储分析

优点:

顺序存储:

  1. 可以实现随机存取。
  2. 每个元素占用最少的空间。

链式存储:

        充分利用所有单元空间,不会出现碎片现象。

缺点:

顺序存储:

        只能使用整块的存储单元,会产出较多的碎片。

链式存储:

  1. 需要额外的存储空间用来存放下一结点的指针。
  2. 只能实现顺序存取。

时间复杂度与空间复杂度

算法

  1. 定义:对特定问题求解步骤的描述
  2. 特性:有穷/稳定/可行/输入/输出

时间复杂度

  1. 指算法中所有语句的频度(执行次数)之和。
  2. T(n) = O(f(n))
    1. n是问题的规模;f(n)是问题规模n的某个函数。
    2. O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
  3. 时间复杂度的计算忽略高阶项系数和低阶项

例子

例子一
int sum  = 0; //执行一次
sum = n * (n +1)/2; //执行一次
printf("%d",sum); //执行一次

 算法的执行次数等于3。时间复杂度T(N)=O(1),表示不会随n的增长而增长。

例子二(2011年计算机联考真题)
int x = 2;
while(x < n / 2){
	x = 2 * x;
}

 执行频率最高的语句为“x = 2 * x;” 设该语句共执行了t次,则2^(t+1) < n/2,故t = log₂(n/2)-1= log₂n-2; 时间复杂度T(n)=O(log₂n)

例子三
int i,x = 2;
for(i = 0;i < n;i++){
	x = 0;
	while(x < n / 2)
		x = 2 * x;
}

 执行频率最高的语句为“x = 2 * x;” 设该语句内层循环执行了log₂n次,外层执行了n次; 时间复杂度T(n)=O(nlog₂n)

例子四
int sum1 = 0,sum2 = 0,i,j;
for(i = 0;i < n;i++)
	sum1 = sum1 + i;
for(j = 0;j < m;j++)
	sum2 = sum2 + j;
printf("%d,%d",sum1,sum2)

 两个循环没有嵌套,串行执行。所以时间复杂度T(n) = O(n)+O(m);取最大的,即时间复杂度T(n) = max(O(n)+O(m))

空间复杂度

  1. 指算法运行过程中所使用的辅助空间的大小
  2. S(n)=O(f(n))
    1. 除了需要存储算法本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。
    2. 若输入数据所占空间只取决于问题本身,和算法无关,这样只需分析该算法在实现时所需的辅助单元即可。
    3. 算法原地工作:算法所需的辅助空间是常量,即O(1)
      1. n个元素数组排序,不适用额外的空间(随着n的增长而增长的空间叫额外空间),空间复杂度是O(1)

相关推荐

  1. C语言强化-1.数据结构概述

    2024-07-23 06:18:03       23 阅读
  2. 第二讲 C语言数据结构与变量(1

    2024-07-23 06:18:03       46 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-23 06:18:03       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-23 06:18:03       106 阅读
  3. 在Django里面运行非项目文件

    2024-07-23 06:18:03       87 阅读
  4. Python语言-面向对象

    2024-07-23 06:18:03       97 阅读

热门阅读

  1. 【Go程序】爬虫获取豆瓣Top250

    2024-07-23 06:18:03       23 阅读
  2. python入门课程Pro(2)--循环

    2024-07-23 06:18:03       21 阅读
  3. 深入剖析Tomcat整体架构

    2024-07-23 06:18:03       27 阅读
  4. CCF GESP Python编程 二级认证真题 2024年6月

    2024-07-23 06:18:03       30 阅读
  5. Android5.1 NAT功能的iptables规则

    2024-07-23 06:18:03       25 阅读
  6. C语言-预处理详解

    2024-07-23 06:18:03       25 阅读
  7. ios CCUIHilightedLabel.m

    2024-07-23 06:18:03       26 阅读
  8. 动态内存管理

    2024-07-23 06:18:03       19 阅读
  9. linux协议栈之FDB表

    2024-07-23 06:18:03       21 阅读