新手天翼
一、时间复杂度
1. 什么是时间复杂度
在计算机科学中，时间复杂**，又称时间复杂度，算法的时间复杂度是一个函数，它定**描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
2. 根据代码的条数计算时间复杂度
#include <iostream>
using namespace std;
int s[10010],n,t; //1条语句
int main(){
cin>>n; //1条语句
for(int i=1;i<=n;i++){ //循环有n条语句
cin>>a[i];
} for(int i=1;i<=n-1;i++){ //取最坏情况，循环有n*n*3条语句
for(int j=i+1;j<=n;j++){
if(a[i]>a[j]){
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
for(int i=1;i<=n;i++){ //循环有n条语句
cout<<a[i]<<" ";
} return 0;
}
以上述代码为例，计算其时间复杂度：
- 算出来的代码的语句条数：3n2 + 2n + 2
- 只保留最高次项：3n2
- 如果最大的一项是常数，则记为1；否则把前面的常数系数去掉： n2
- 将结果套上 O() 标记
可以得到上述代码的时间复杂度为: O(n2)
实际上，我们发现在计算时间复杂度时，如果代码中有循环结构，只要考虑循环次数最多的循环即可。 上述代码只需要考虑代码中间部分的双重循环即可。
3. 几种排序的时间复杂度
选择排序 O(n^2);
冒泡排序 O(n^2);
插入排序 O(n^2);
桶排序 O(n);
4. 评判是否超时
一般10^8 是一个临界点，当时间超过10^8 时，会超时；在10^8 以内则不会。10^8 左右时可能会超时。
二、链表
1. 基本概念
- 链表是一种线**表
- 链表中，除了第一个元素没有前驱，最后一个元素没有后继以外，其它每一个元素都有唯一的前驱和后继。
2. 线**表
链表和数组都属于线**表，区别是
- 数组在计算机中是连续分配内存的
- 链表在计算机中不是连续分配内存
3. 链表元素的组成
链表中的每一个元素至少由两部分组成，C语言中一般使用结构体实现：
- 存放值的数据域
- 存放下一个元素地址的地址域
- 地址相当于变量在计算机内存里的“门牌号码
4. 链表首尾元素
链表中第一个元素没有前驱，我们使用一个头指针指向它的位置，头指针是一个专门存储地址的变量。
链表中最后一个元素没有后继，我们在它的地址域放入一个
空地址，NULL
5. 链表的特点
链表由于在内存中不是连续存储的，所以：
- 不能直接计算出某一个元素的地址，所以不支持随机访问第i个元素。每次查询某个元素需要遍历整个链表，时间复杂度为O(n)。
- 插入和删除元素不需要移动后面的元素，只需要修改一些元素的地址域，时间复杂度为O(1)。但是查找到插入和删除的位置需要花时间。
6. 链表的插入操作
链表中，假设我们要在a和b之间插入一个p，要分2步完成：
- 将p的地址域赋值为b的地址
- 修改a的地址域为p的地址
注意：两步的顺序不能颠倒
7. 链表的删除操作
链表中，假设我们要把a和b之间的结点p删除，需要将a的地址
域赋值为p的地址域
通常还跟着一步：删除结点p，释放点p的内存空间。
8. 双向链表
有的链表中，每个元素不仅有存储后继的地址域，还有存储其前驱的地址域。这样的链表叫双向链表。
9. 循环链表
有的链表中，最后一个元素的后继不是NULL，而是链表的第一个元素。这样的链表叫循环链表。
三、STL中的list
1. STL是什么
STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。
C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。
2. list（链表）
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的**节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. 如何使用list
头文件
#include <list>
定义： List<数据类型> 链表名;
例：
list<int> l1; //定义一个int型的链表l1
list<double> l2; //定义一个double型的链表l2
struct point{
int x,y;
}
list<point> l3; //定义一个（结构体）point型的链表l3
求链表长度与遍历链表
- 求链表长度：l.size()
- 遍历链表
1）定义一个迭代器it，指向链表开头（l.begin()）
list<int> l; list<int>::iterator it=l.begin();
2）当迭代器没有到达链表尾部（l.end()），迭代器it往后移动
while(it!=l.end()) it++; //注意不能写it<l.end()
3) 输出迭代器指向的元素
cout<<*it<<' ';
迭代器it指向的是元素地址，*it则是该地址对应的元素。
向链表中插入新元素
- 向链表尾部插入新元素e：
l.push_back(e);
- 向链表某个元素前插入新元素，例如在值为x的元素前插入一个值为e的新元素：
list<int> l;
list<int>::iterator=l.begin();
while(it!=l.end() && *it!=x) it++; //先找到值为x的元素的位置
l.insert(it,e); //在该元素之前插入值为e的元素，此函数的返回值是一个指向新元素e的迭代器
从链表中删除某个元素
假设从链表中删除一个值为e的元素：
list<int> l; list<int>::iterator=l.begin();
while(it!=l.end() && *it!=e) it++; //先找到值为e的元素的位置
l.erase(it); //删除该元素，此函数会返回指向被删除元素后一个元素的迭代器
武奕楷在2021-11-12 18:17:40追加了内容
还有，链表和队列（也就是张欣悦发的那个东东）很像，没有下标！！！
武奕楷在2021-11-13 15:18:32追加了内容
递推问题：
（1） 状态
例：兔子繁殖问题中
f[i]表示第i个月兔子的数量
(2) 状态关系式（说专业一点也就是 状态转移方程）
f[i]=f[i-1]+f[i-2];
（3）边界
f[1]=1;
f[2]=1;
（4）目标
f[n] 第n个月兔子的数量
斐波那契数列不超过46项，可以用int存储
斐波那契数列不超过91项，可以用long long存储
主要类型：斐波那契数列
斐波那契数列类型例题1
斐波那契数列类型例题2
斐波那契数列类型例题3
武奕楷在2021-11-13 16:39:16追加了内容
递推问题：
（1） 状态
例：兔子繁殖问题中
f[i]表示第i个月兔子的数量
(2) 状态关系式（说专业一点也就是 状态转移方程）
f[i]=f[i-1]+f[i-2];
（3）边界
f[1]=1;
f[2]=1;
（4）目标
f[n] 第n个月兔子的数量
斐波那契数列不超过46项，可以用int存储
斐波那契数列不超过91项，可以用long long存储
主要类型：斐波那契数列
斐波那契数列的模板代码为
#include<iostream>
using namespace std;
int a[50],n;//如果n超过46且小于等于92，用long long，a[]定义为a[95]
int main(){
a[1]=1;
a[2]=1;
cin>>n;
for(int i=3;i<=n;i++){
a[i]=a[i-1]+a[i-2];
}
cout<<a[n];
return 0;
}
斐波那契数列类型例题1
难度：简单，直接套上面的状态关系式。
斐波那契数列类型例题2
难度：简单，直接套上面的状态关系式。注意需要用long long
斐波那契数列类型例题3
难度：中等偏下 把边界改成f[1]=1,f[2]=2,再套公式。而且要注意需要用long long
