🌺博客汇总：🌃Summary And Schedule🌠

🌸考研相关内容汇总：考研Schedule&&Summary

🌼408王道C督学课程目录：《王道C语言督学班目录》

本章需要掌握：

  • 1、逻辑结构是什么？存储结构是什么？
  • 2、T(n)时间复杂度的简单计算
  • 3、S(n)空间复杂度为O(1)代表什么？

0、与408关联（选择+大题）

本章需要掌握：

部分卷子小题也会考到时间复杂

基本上考到数据结构大题都需要设计算法的时间复杂度

1、逻辑结构与存储结构

逻辑结构（抽象的）：数据元素之间的逻辑关系。有集合结构、线性结构、树形结构、图形结构。

存储结构（具体的）：数据结构在计算机中的表示。有顺序存储、链式存储、索引存储、散列存储。

顺序存储 链式存储
优 随机存取 充分利用存储单元
元素占空间少 不会出现碎片现象
缺 只能使用整块的存储空间 需要额外的空间存放指针
会出现碎片现象 只能实现顺序存取

2、时间复杂度与空间复杂度

算法：对特定问题求解步骤的描述

算法的特征：有穷、确定、可行、输入、输出

时间复杂度：所有语句的频度（执行次数）之和。 T(n)=O(f(n))

复杂度排序

时间复杂度的计算忽略高阶项系数和低阶项，计算一般设最高频语句执行k次或找规律。

空间复杂度：会判断是不是O(1)就可以了，空间复杂度O(1)的意思是，n个元素排序，不使用额外的空间（随着n增长而增长的空间）。 S(n)=O(f(n))