1.数据结构
1.1什么是数据结构？
在计算机科学中，数据结构是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构就是数据的组织形式，研究的就是把数据按照何种形式存储在计算机中。
1.2为什么会有数据结构
- 随着计算机的发展和应用范围的拓宽，计算机需要处理的数据量越来越大，数据类型越来越多，数据之间的关系也越来越复杂。
- 这就要求人们对计算机加工处理的数据进行系统的研究，即研究数据的特性、数据之间存在的关系，以及如何有效的组织、管理存储数据，从而提高计算机处理数据的效率。
- 数据结构这门学科就是在此背景上逐渐形成和发展起来的。
数据结构研究的是数据本身的特性、数据与数据之间的关系，以及如何在计算机中存储数据，从而高效的处理这些数据。
1.3数据结构的三要素
1.3.1逻辑结构
数据中各元素之间的逻辑关系。
它只关心数据中各个元素之间的关系，并不关心数据是怎么在内存中存储的。
常见的逻辑结构：
1.集合
所有的数据只是在一个集合中，彼此之间再没有其它的联系。
2.线性结构
数据之间只存在一对一的关系。
3.树形结构
数据之间是一对多的关系。
4.图结构
1.3.2存储结构
存储结构又称物理结构，存储结构顾名思义，就是数据在计算机中如何存储的。
1.顺序结构
把逻辑上相邻的元素存储在物理上也相邻的存储单元中。——数组。
2.链式结构
通过指针来存储前一个或下一个数据元素的地址，从而实现元素和元素之间的关系。
1.3.3数据的运算
数据的运算（针对数据的各种操作），包括数据结构的实现，以及基于数据结构上的各种操作。
各种操作：
- 创建这个数据结构
- 增加数据
- 删除数据
- 查找数据
- 修改数据
- 排序数据
- 输出数据
- ……
总结：创+增删查改+其他
2.算法
2.1什么是算法？
算法（Algorithm）是指解题方案的准确而完整的描述，是⼀系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
- 算法是可以没有输入的，一定要有输出。没有输出的算法是没有意义的。
简单来说算法就是一系列的步骤，用来将输入数据转化成输出结果。
2.2算法的好坏程度
算法A：
const int N = 1e5 + 10; int a[N]; int sum(int n) {// 先把 1 ~ n 存起来for(int i = 1; i <= n; i++){a[i] = i;}// 循环逐个数字相加int ret = 0;for(int i = 1; i <= n; i++){ret += a[i];}return ret; }需要开辟一个大小为N的空间。
算法B：
int sum(int n) {// 循环逐个数字相加int ret = 0;for (int i = 1; i <= n; i++) {ret += i;}return ret; }不需要开辟一个大小为N的空间。
需要循环n次，ret+=n语句会执行n次而且随着问题规模的增长，执行次数也会增长。
算法C：
int sum(int n) {// 利⽤求和公式return (1 + n) * n / 2; }不论问题规模n为多少，(1+n)*n/2语句只会执行1次。
算法中基本语句总的执行次数与问题规模n有关。因此可以根据算法执行过程中，所有语句被执行的次数之和来衡量算法的好坏，这就是时间复杂度。
2.3时间复杂度
在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量描述了该算法的运行时间。这个T(N)函数式计算了程序中语句的执行次数。
案例1：
void fun(int N)
{ int count = 0; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { ++count; // 执⾏次数是 n*n，也就是 n^2} } for(int k = 0; k < 2 * N; k++) {++count; // 执⾏次数是 2*n} int M = 10; while(M--) { ++count; // 执⾏次数 10}
}语句的总执行次数：
T(N)=N^2+2*N+10
- 当N=10时， T(N)=100+20+10=130
- 当N=100时，T(N)=10000+200+10=10210
- 当N=1000时，T(N)=1000000+2000+10=1002010
- 当N=10000时，T(N)=100000000+20000+10=100020010
2.3.1大O表示法
在上述案例中，对N取值进行分析，随着N的增大，对结果影响最大的一项是N^2。
因此，在计算时间复杂度的时候，一般会把T(N)中对结果影响不大的项忽略掉，这种表示时间复杂度的方式称为 大O渐进时间复杂度-粗略估计方式，只看影响时间开销最大的一项。
所以上述式子应该取最高项：O(N^2)
推导大O渐进时间复杂度的规则：
- 时间复杂度函数式T(N)中，只保留最高阶项，去掉那些最低阶项；
- 如果最高阶项存在且不是1，则去除这个项目的常数系数；
- T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。
2.3.2最优、平均和最差时间复杂度
案例：在n个整形元素数组中，检测x是否存在，若存在返回其在数组中的下标，否则返回-1
int find (int a[], int n, int x)
{for (int i = 0; i < n; i++){if (a[i] == x) return i;}return -1;
}
在查找过程中，需用x与数组中元素依次比较，因此总的比较次数就是该算法的时间复杂度。
- 若待查找元素x为21，只需要比较1次，为算法最优情况。
- 若待查找元素x为17，或者是不存在的元素，需要比较n次，为算法的最坏情况。
- 所有情况的比较次数之和，除以总情况，为算法的平均情况。
因此算法：
- 最好时间复杂度：O(1)
- 最坏时间复杂度：O(N)
- 平均时间复杂度：O((1+n)/2)，也就是O(N)
2.3.3时间复杂度计算案例
案例1：
void func1(int N)
{int count = 0;for(int k = 0; k < 2 * N; k++){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}总执行次数的数学表达式为：f(n)=n*2+10；
保留最高阶项，省略最高项的系数后的大O渐进表示法为：O(n)。
案例2：
void func2(int N)
{int count = 0;for (int k = 0; k < 1000; k++){++count;}printf("%d\n", count);
}总执行次数的数学表达式为：f(n)=1000;
不论n如何变化，总执行次数都是1000，故时间复杂度为：O(1)。
案例3：
void func3(int m, int n)
{for (int i = 0; i < m; i++){printf("hello\n");}for (int i = 0; i < n; i++){printf("hello\n");}
}总的执行次数为f(m,n)=m+n；
m和n的变化都是影响基本语句执行次数，即m和n都是问题规模，故时间复杂度为O(m+n)
案例4：
void func4(int m, int n)
{for (int i = 0; i < m; i++){for(int j = 0; j < n; j++){printf("%d, ", i);}printf("\n");}
}总的执行次数为f(m,n)=m*n；
m和n的变化都是影响基本语句执行次数，即m和n都是问题规模，故时间复杂度为O(m*n)
案例5：
void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}假设执行次数为x，则2^x=n；因此执行次数：x=logn
案例6：
// ⽤递归计算 N 的阶乘
long long fac(int N)
{if(N == 0) return 1;return fac(N - 1) * N;
}递归算法时间复杂度求解方式为，单次递归时间*总的递归次数
注：这里只是简易估算方式，递归算法时间复杂度严谨的计算方法是利用主定理来求得递归算法的时间复杂度。
fac(5)需要递归6次，则fac(n)就需要递归n+1次，故递归求阶乘的时间复杂度为O(n)。
2.4空间复杂度
在算法竞赛中，空间复杂度就是整个程序在解决这个问题时，一共使用了多少空间。
案例一：冒泡排序
#include <iostream>
using namespace std;
const int N = 20;
int arr[N];
int main()
{int n = 0;cin >> n;int i = 0;//输⼊for(i=0; i < n; i++)cin >> arr[i];//排序for(i = 0; i < n-1; i++){int j = 0;for(j = 0; j <= n-1-i; j++){if(arr[j] < arr[j+1]){int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp; }}} //输出for(i=0; i < n; i++){cout << arr[i] << endl;}return 0;
}空间复杂度：需要一个和问题规模一致的数组来存数据。因此空间复杂度为O(N)。
案例二：递归求阶乘
// 计算递归求阶乘Fac算法的空间复杂度？
long long fac(int N)
{if (N == 0) return 1;return fac(N - 1) * N;
}递归算法空间复杂度求解方式，单次递归空间复杂度*递归次数。
2.5常见复杂度的增长对比
2.6算法竞赛中的时间限制和空间限制
- 信息学竞赛中，C++通常设定1到2秒的时间限制，要控制运行次数在10^7至10^8之间
- 空间限制在128MB或256MB，可以开一个3*10^7大小的int类型数组，或者5000*5000大小的二维数组
3.STL
3.1C++标准库
C++标准是C++编程语言的规范，由国际标准化组织（ISO）制定。
每一个版本的C++标准不仅规定了C++的语法、语言特性，还规定了一套C++内置库的实现规范，这个库便是C++标准库。C++标准库中包含大量常用代码的实现，如输入输出、基本数据结构、内存管理、多线程支持等。
我们可以这样理解，C++给我们提供了一大堆的代码，这些代码里面包含特别多已经实现好的数据结构和算法。
3.2什么是STL?
STL，全称为Standard Template Library（标准模板库），是C++编程语言中不可或缺的一部分，它为程序员提供了高效且灵活的数据结构和算法。STL的主要目标是提高代码的可读性、可维护性和性能，通过使用泛型编程（Generic Programming）理念，实现了数据结构和算法的分离，使得代码更易于复用。
由于其模板化的特点，它能够兼容自定义的数据类型，避免大量的重复。
