一.时间复杂度
1.概念
算法的时间复杂度是衡量一个算法运行时间和数据规模关系的函数。时间复杂度一般是用大O计算法来表示。计算时间复杂度可以帮助我们分析这个算法是否可以高效通过所有数据点哦~
2.衡量规则
时间复杂度用大O计数法来表示，一般写作O(...)，括号内为与数据规模相关的函数表达式。
Ⅰ.循环
其实算法效率低下有一个大原因是循环次数太多了(⊙o⊙)!如果有k层循环，每层都循环n次的话，时间复杂度是O(n^k^)。
Ⅱ.数量级
时间复杂度只关注时间和数量级的关系。循环次数分别为3n，n+5，n/2次，但它们的时间复杂度均记作O(n)。
Ⅲ.高阶指数
如果一个算法中包含多个不同阶的执行次数，那我们只关注最高阶的指数。
Ⅳ.多变量情况
如果影响时间复杂度的变量很多，时间复杂度就记作O(nm)。
3.常见的时间复杂度比较
O(1)<O(logn)<O(√n)<O(n)<O(nlogn)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)
二.数据结构-vector动态数组
1.概念
vector是一种存储数据的容器，可以存储一组相同类型的数据，下标默认从0开始，优点是长度可以动态改变，各种操作方法配置齐全，使用很方便，缺点是速度略慢于普通数组。
2.vector的创建
vector<类型> 名字;
vector<int> v; // 创建一个int类型一维的空动态数组
vector<int> v(n,x); // 创建一个int类型一维动态数组，初始长度n，值为x。
vector<int> v[N]; // 创建一个int类型二维的动态数组，其中一维长度为N，二维长度可变
vector<vector<int>> v(n,vector<int>(m,x)) // 创建一个int类型n行m列的二维动态数组，初始值为x
3.vector的常用操作函数
vector<int> v;
v.push_back(x); // 把元素x添加到末尾
v.pop_back(); // 把末尾元素删除
v.size(); // 返回长度
v[i]; // 获取下标为 i 的元素
v.front(); // 获取首位元素，也可以使用下标 v[0]
v.back(); // 获取末尾元素，也可以使用下标 v[v.size()-1]
v.clear(); // 清空容器
v.begin(); // 返回一个迭代器，指向容器的第一个元素
v.end(); // 返回一个迭代器，指向容器的最后一个元素的后一位
v.erase(v.begin()+1, v.begin()+4); // 删除容器中下标 1~4 的元素，删除的时间复杂度是O(n)
三.数据结构-stack栈
1.概念
Stack栈是一种基于 后进先出原则的数据结构，它是一种线性表。
2.STL栈的用法
#include<stack>
stack<int> stk; // 创建int类型栈，名字为stk
stk.push(x) // 把x压栈
stk.pop() // 弹出栈顶元素
stk.top() // 查看栈顶元素
stk.size() // 返回栈内元素个数
stk.empty() // 返回栈是否为空
四.数据结构-queue队列
1.概念
Queue队列是一种常见的数据结构，它遵循 先进先出的原则。
2.STL队列用法
#include<queue>
queue<int> q;
q.push(x); // 队尾插入x
q.pop(); // 弹出队头
q.front(); // 查看队头
q.back(); // 查看队尾
q.size(); // 查看q元素个数
q.empty(); // 查看q是否为空
五. 数据结构-set和unordered_set集合
1.概念
set 是按照特定顺序存储唯一元素的容器，即自带排序和去重。它可以同时兼顾查找、插入和删除。元素放入 set 后不支持修改，但可以删除。
2.set的常用操作方法
set<int> s;
s.insert(x);// 当容器中没有等价元素的时候，将元素 x 插入到 set 中。
s.erase(x);// 删除值为 x 的所有元素，返回删除元素的个数。
s.clear();// 清空 set。
s.count(x);// 返回 set 内键为 x 的元素数量。
s.find(x);// 在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end()。
s.empty();// 返回容器是否为空。
s.size();// 返回容器内元素个数。
3.set的输出方法
set<int> s;
s.insert(1);
s.insert(3);
s.insert(6);
for (auto it:s)
cout << it << " ";
for (auto it = s.begin(); it!=s.end(); it++)
cout << *it << " ";
六.数据结构-map和unordered_map哈希表
1.概念
map 是有序键值对容器（自动按照键排序），它的元素的键是唯一的。搜索、移除和插入操作均拥有对数复杂度。可以把map理解成高级的桶数组，桶数组只能实现 int --> int 的映射，map则不受限制。
2.map的常用操作方法
map<int,int> mp;
mp[3] = 5; // 通过赋值创建一个键值对映射
mp[4] = 2;
mp[2] = 7;
mp.erase(4); // 删除{4，2}这个键值对
cout << mp.count(2); // 输出1，表示2这个键存在
cout << mp.count(5); // 输出0，表示5这个键不存在
// 枚举型遍历访问map的所有键值对
for (auto it : mp)
{
cout << it.first << " " << it.second << endl;
}
