【算法】算法基础与 STL

时间复杂度

时间复杂度是算法中基本操作执行次数的数量

时间复杂度排序为

在一般的算法测评机中, 大约 1 秒钟能够执行 $510^8$ 条指令, 也就是说对于 $O(n^2)$ 时间复杂度的算法, 假设 $n$ 最大为 $10^5$, 那么需要的时间最大为 ${(10^{5})}^2/510^8$ 约为 20 秒运行完毕. 在做题的过程中要提前计算运行时间来选择合适复杂度的算法.

空间复杂度

空间复杂度是运行时所需空间的度量

对于空间复杂度, 除了要计算所给限制以外, 还需要记忆各个类型最大值, 如下

C,C++中常见的数值范围

避免在写代码时发生类型上溢导致判题不通过.

常见的 STL 容器

Vector

1
2
3
4
5
6
7
8
9
10
#include<vector>
vector<int> vec;    //定义
vec.push_back(a);   //往后添加元素
vec.insert(vec.begin()+1,2);  //在下标[1]处插入 2  
vec.pop_back();     //移除末尾元素
vec.erase(vec.begin()+1);   //删除下标[1]处元素
vec.resize(3)   //只保留前 3 个元素
vec.size()  //判断容器大小
vec.front() //获取首元素
vec[0]  //访问数组

set

set 是集合元素, 会自动剔除重复元素, 内部是由红黑树构成的, 在插入元素时会自动帮你排序

1
2
3
4
5
6
7
8
9
10
11
#include<set>
set<int> s  //定义
s.insert(10)    //插入元素
s.count(10) //判断元素是否存在
//遍历 set
set<int>::iterator it;
for(it=s.begin();it!=s.end();it++){
    cout<<*it<<endl;
}
//遍历 set(简写)
for(int i:s) cout<<i<<endl;

map

map 是映射集合, 内部由红黑树实现, 在插入元素时会自动平衡树且帮你排序, map 与 vector 相比, 除了数据结构不同, 最大的不同点就是按值查询的复杂度不同, 由于 map 是根据平衡二叉树实现的, 所以单次查找的时间复杂度为 $O(logn)$,如果 vector 没有排序,那么 而 vector 单次查找要遍历数组, 时间复杂度为 $O(n)$ , 如果加上排序的话二分查找的时间复杂度就是 $O(logn)$, 所以其实 vector 在大部分情况下已经可以代替 map 的使用, map 在插入或者删除时还要 new 和 delete 一个映射, 所带来的时间开销也是显著的, map 一般用于数据量不大，且需要有序的访问键值对时使用.

在不要求顺序查找时可以使用 unordered_map, 能够在不排序的情况下有 $O(logn)$ 复杂度的查找.

1
2
3
4
5
map<int, int> m;    //定义 map, 前面是键名后面是键值
m[1] = 100; //赋值
m[1] = 200; //修改值
m.count(10);    //计数,复杂度为 logn
m.find(10); //返回该元素对应的迭代器,如果不存在返回 end()

例题

使用 STL 的 set 容器去存储每一个字符串, 然后排序输出即可. 需要注意的是这里使用了 sstream 来读取字符流, sstream 可以将字符流中的字符以空格分开, 然后逐步赋值给其他变量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<set>
#include<string>
#include<sstream>
using namespace std;
set<string> dict;
int main(){
    string s,buf;
    while(cin>>s){
        for(int i=0;i<s.length();i++){
            if(isalpha(s[i]))
                s[i] = tolower(s[i]);
            else
                s[i] = ' ';
        }
        stringstream ss(s);
        while(ss>>buf){
            dict.insert(buf);
        }
        for(string str:dict){
            cout<<str<<endl;
        }
    }
    return 0;
}