数据结构：绪论之时间复杂度与空间复杂度
作者主页
失踪人口回归，陆续回三中。
开辟文章新专栏——数据结构，恳请各位大佬批评指正！
文章目录
数据结构的基本知识
数据：
数据是信息的载体
数据元素：
数据元素是数据的基本单位，数据项是构成元素不可分割的最小单位。
数据对象：
具有相同性质的数据元素的集合
数据类型：
- 原子类型
- 结构类型
- 抽象数据类型（ADT）:描述了数据的逻辑运算和抽象运算，从而构成一个完整的数据结构定义
数据结构：
有一种或多种特定关系的数据元素的集合
逻辑结构：元素之间的逻辑关系
集合：元素同属于一个集合
线性结构：一对一，除了第一个元素，所有元素都有唯一先驱，除了最后一个元素，所有元素都有唯一后继
树形结构：一对多
网状结构：多对多
存储结构：物理结构
顺序存储：数据存储在相邻存储单元中，可以实现随机存储，但是外部碎片多
链式存储：利用存储地址的指针来表示元素之间的逻辑关系，不会出现碎片现象，但是要存储指针占用额外空间，只能实现顺序存取
索引存储：检索快，但索引表占用额外空间，增删数据时也要修改索引表，花费时间较多
散列存储：根据元素的关键字直接计算出该元素存储地址，也称哈希存储。快，但是如果散列函数不好，会导致冲突浪费时间
数据运算
算法与其评价
算法的概念：
是对特定问题求解步骤的一种描述。程序=数据结构+算法（步骤）
算法具有：有穷性，确定性，可行性，输入，输出
算法是有穷的，程序是无穷的
一个好的算法应该具备：正确性，可读性，健壮性，高效率与低存储量需求
算法效率的评价：
时间复杂度
- 定义：衡量算法执行时间随输入规模增长的变化趋势，不关注具体执行时长，关注的是输入规模变大时，算法运行时间的增长快慢。
- 计算规则：
- 只保留常数项
- 保留最高项
- 乘法规则：如果一个算法是嵌套结构，外层操作数量级是(f(n))，内层是(g(n))，那么整体时间复杂度就是两者相乘 。比如外层循环n次，内层循环m次，整体时间复杂度就是(O(n×m)) 。
- 如何计算：顺序执行的代码只会影响常数项，可以忽略只需挑循环中的一个基本操作分析它的执行次数与n的关系即可如果有多层嵌套循环，只需关注最深层循环几次就行了
- 三种复杂度：最坏时间复杂度：考虑输入数据“最坏的情况”，执行次数最多的时候平均时间复杂度：考虑所有输入数据都等概率出现的情况最好时间复杂度：考虑输入数据的最好的情况，
量级比较：“常对幂指阶” 是常见时间复杂度量级从小到大的排序，也是保留阶数最高的依据。
加法规则：当一个算法由多个部分组成时，这意味着在计算总时间复杂度时，取各部分时间复杂度中量级最大的那个。例如，算法一部分时间复杂度是(O(n))，另一部分是(O(n2))，整体时间复杂度就是(O(n2)) 。
voidloveyou(int n){//1次int i =1;//3001次while(i<=n){//3000*2次 i++;printf("i love you ");}}intmain(){loveyou(3000)}//T（n）=1+3001+3000*2//T(n)=3n+3常用技巧
表述方法：用大 O 符号（Big O notation）表示，如 O (1)、O (n)、O (n²) 等。通过分析算法中基本操作的执行次数与输入规模 n 的关系来确定，忽略低阶项和常数系数，保留最高阶项表示量级 。
空间复杂度
- 空间复杂度的定义：空间复杂度（Space Complexity）是衡量算法在执行过程中临时占用存储空间大小的量度。它反映了算法所需存储空间与输入数据大小之间的关系。空间复杂度通常用大O表示法来表示。2.2 空间复杂度的分析同时间复杂度一样用大O表示法表示；也是表示一个数量级。记作：
- 2.3 常见的空间复杂度常数阶：如果算法的空间复杂度不随问题规模 n 的变化而变化，即算法所需的存储空间是一个常数，那么空间复杂度为 O(1)。线性阶：如果算法所需的存储空间与问题规模 n 成正比，即算法所需的存储空间随着 n 的增加而线性增加，那么空间复杂度为O(n)。多项式阶：如果算法所需的存储空间与问题规模 n 的关系可以表示为多项式函数，即空间复杂度为 O(n^k)，其中 k 是一个正整数。对数阶：如果算法所需的存储空间与问题规模 n 的关系可以表示为对数函数，即空间复杂度为 O(log n)。指数阶：如果算法所需的存储空间与问题规模 n 的关系可以表示为指数函数，即空间复杂度为 O(2^n)。
多项式函数，即空间复杂度为 O(n^k)，其中 k 是一个正整数。
对数阶：
如果算法所需的存储空间与问题规模 n 的关系可以表示为对数函数，即空间复杂度为 O(log n)。
指数阶：
如果算法所需的存储空间与问题规模 n 的关系可以表示为指数函数，即空间复杂度为 O(2^n)。
