算法的概念

何为算法

算法是求解问题的一系列计算步骤，用来将输入数据转换成输出结果。

算法的五大特征

1.有限性
2.确定性
3.可行性
4.输入性（有零个或多个输入）
5.输出性（有一个或多个输出）

算法设计的基本步骤

算法与数据结构

算法与数据结构既有联系又有区别。
联系：数据结构是算法设计的基础。算法的操作对象是数据结构，在设计算法时，通常要构建适合这种算法的数据结构。数据结构设计主要是选择数据的存储方式，如确定求解问题中的数据采用数组存储还是采用链表存储等。算法设计就是在选定的存储结构上设计一个满足要求的好算法。
区别：数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。

算法分析

算法时间复杂度

一个算法是由控制结构（顺序、分支和循环）和原操作（固有数据类型的操作）构成的，算法的运行时间取决于两者的综合效果。

算法空间复杂度

一个算法的存储量包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时，只考察临时变量所占空间。

渐进符号（O、Ω和θ）

定义1（大O符号） f(n)=O(g(n))（读作“f(n)是g(n)的大O”）当且仅当存在正常量c和n₀，使当n≥n₀时，f(n)≤cg(n)，即g(n)为f(n)的上界。
定义2（大Ω符号） f(n)=Ω(g(n))（读作“f(n)是g(n)的大Ω”）当且仅当存在正常量c和n₀，使当n≥n₀时，f(n)≥cg(n)，即g(n)为f(n)的下界。
定义3（大θ符号） f(n)=θ(g(n))（读作“f(n)是g(n)的大θ”）当且仅当存在正常量c₁、c₂和n₀，使当n≥n₀时，有c₁g(n)≤f(n)≤c₂g(n)，即g(n)与f(n)的同阶。

算法设计工具——STL

STL概述

STL主要由container（容器）、algorithm（算法）和iterator（迭代器）三大部分构成，容器用于存放数据对象（元素），算法用于操作容器中的数据对象。

何为STL容器

一个STL容器就是一种数据结构，如链表、栈和队列等，这些数据结构在STL中都已经实现好了，在算法设计中可以直接使用它们。

数据结构	说明	实现头文件
向量（vector）	连续存储元素。底层数据结构为数组，支持快速随机访问	<vector>
字符串（string）	字符串处理容器	<string>
双端队列（deque）	连续存储的指向不同元素的指针所组成的数组。底层数据结构为一个中央控制器和多个缓冲区，支持首尾元素（中间不能）快速增删，也支持随机访问	<deque>
链表（list）	由结点组成的链表，每个结点包含着一个元素。底层数据结构为双向链表，支持结点的快速增删	<list>
栈（stack）	后进先出的序列。底层一般用deque（默认）或者list实现	<stack>
队列（queue）	先进先出的序列。底层一般用deque（默认）或者list实现	<queue>
优先队列（priority_queue）	元素的进出队顺序由某个谓词或者关系函数决定的一种队列。底层数据结构一般为vector（默认）或者deque	<queue>
集合（set）/多重集合（multiset）	由结点组成的红黑树，每个结点都包含着一个元素，set中所有元素有序但不重复，multiset中所有关键字有序但不重复	<set>
映射（map）/多重映射（multimap）	由（关键字，值）对组成的集合，底层数据结构为红黑树，map中所有关键字有序但不重复，multimap中所有关键字有序但可以重复	<map>

为此，使用STL时必须将下面的语句插入到源代码文件开头：

using namespace std;

这样直接把程序代码定位到std命名空间中。

何为STL算法

STL算法是用来操作容器中数据的模板函数，STL提供了大约100个实现算法的模版函数。
STL算法部分主要由头文件<algorithm>、<numeric>和<functional>组成。

例：以下程序使用STL算法sort()实现整型数组a的递增排序：

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{int a[] = {5,9,3,4,7,6};sort(a,a+6);for(int i=0;i<6;i++){printf("%d ",a[i]);}printf("\n");return 0;
} 

运行结果为：

何为STL迭代器

STL迭代器用于访问容器中的数据对象。每个容器都有自己的迭代器，只有容器自己才知道如何访问自己的元素。迭代器像C/C++中的指针，算法通过迭代器来定位和操作容器中的元素。
常用的迭代器：

迭代器	作用
iterator	指向容器中存放元素的迭代器，用于正向遍历容器中的元素。
const_iterator	指向容器中存放元素的常量迭代器，只能读取容器中的元素。
reverse_iterator	指向容器中存放元素的反向迭代器，用于反向遍历容器中的元素。
const_reverse_iterator	指向容器中存放元素的常量反向迭代器，只能读取容器中的元素。

迭代器的常用运算

++：正向移动迭代器。

–：反向移动迭代器。

*：返回迭代器所指的元素值。

常用STL容器

顺序容器

1）vector（向量容器）
它是一个向量类模板。向量容器相当于数组。用于存储具有相同数据类型的一组元素，可以从末尾快速的插入与删除元素，快速地随机访问元素，但是在序列中间插入、删除元素较慢，因为需要移动插入或删除处后面的所有元素。
定义vector容器的几种方式如下：

vector<int> v1;		//定义元素为int的向量v1
vector<int> v2(10);		//指定向量v2的初始大小为10个int元素
vector<double> v3(10，1.23);	//指定v3的10个初始元素的初值为1.23
vector<int> v4(a，a+5);	//用数组a[0..4]共5个元素初始化v4

vector主要的成员函数

empty()：判断当前向量容器是否为空。

size()：返回当前向量容器的中的实际元素个数。

[]：返回指定下标的元素。

reserve(n)：为当前向量容器预分配n个元素的存储空间。

capacity()：返回当前向量容器在重新进行内存分配以前所能容纳的元素个数。

resize(n) ：调整当前向量容器的大小，使其能容纳n个元素。

push_back()：在当前向量容器尾部添加了一个元素。

insert(pos，elem)：在pos位置插入元素elem，即将元素elem插入到迭代器pos指定元素之前。

front()：获取当前向量容器的第一个元素。

back()：获取当前向量容器的最后一个元素。

erase()：删除当前向量容器中某个迭代器或者迭代器区间指定的元素。

clear()：删除当前向量容器中所有元素。

迭代器函数：begin()、end()、rbegin()、rend()。

2）string（字符串容器）
string是一个保存字符序列的容器，所有元素为字符类型，类似vector<char>。除了有字符串的一些常用操作以外，还有包含了所有的序列容器的操作。字符串的常用操作包括增加、删除、修改、查找比较、连接、输入、输出等。
创建string容器的几种方式如下：

char cstr[]="China! Greate Wall";	//C-字符串
string s1(cstr);			// s1:China! Greate Wall
string s2(s1);				// s2:China! Greate Wall
string s3(cstr，7，11);		// s3:Greate Wall
string s4(cstr，6);			// s4:China!
string s5(5，'A');			// s5:AAAAA

string主要的成员函数

empty()：判断当前字符串是否为空串。

size()：返回当前字符串的实际字符个数（返回结果为size_type类型）。

length()：返回当前字符串的实际字符个数。

[idx]：返回当前字符串位于idx位置的字符，idx从0开始。

at(idx)：返回当前字符串位于idx位置的字符。

compare(const string& str)：返回当前字符串与字符串str的比较结果。在比较时，若两者相等，返回0；前者小于后者，返回-1；否则返回1。

append(cstr)：在当前字符串的末尾添加一个字符串str。

insert(size_type idx，const string& str) ：在当前字符串的idx处插入一个字符串str。

迭代器函数：begin()、end()、rbegin()、rend()。

3）deque（双端队列容器）
它是一个双端队列类模板。双端队列容器由若干个块构成，每个块中元素地址是连续的，块之间的地址是不连续的，有一个特定的机制将这些块构成一个整体。可以从前面或后面快速插入与删除元素，并可以快速地随机访问元素，但删除元素较慢。
定义deque双端队列容器的几种方式如下：

deque<int> dq1;	//定义元素为int的双端队列dq1
deque<int> dq2(10);	//指定dq2的初始大小为10个int元素
deque<double> dq3(10，1.23);//指定dq3的10个初始元素的初值为1.23
deque<int> dq4(dq2.begin()，dq2.end());	//用dq2的所有元素初始化dq4

deque主要的成员函数

empty()：判断双端队列容器是否为空队。

size()：返回双端队列容器中元素个数。

push_front(elem)：在队头插入元素elem。

push_back(elem)：在队尾插入元素elem。

pop_front()：删除队头一个元素。

pop_back()：删除队尾一个元素。

erase()：从双端队列容器中删除一个或几个元素。

clear()：删除双端队列容器中所有元素。

迭代器函数：begin()、end()、rbegin()、rend()。

4）list（链表容器）
它是一个双链表类模板。可以从任何地方快速插入与删除。它的每个结点之间通过指针链接，不能随机访问元素。
定义list容器的几种方式如下：

list<int> l1;			//定义元素为int的链表l1
list<int> l2 (10);		//指定链表l2的初始大小为10个int元素
list<double> l3 (10，1.23);	//指定l3的10个初始元素的初值为1.23
list<int> l4(a，a+5);		//用数组a[0..4]共5个元素初始化l4

list主要的成员函数

empty()：判断链表容器是否为空。

size()：返回链表容器中实际元素个数。

push_back()：在链表尾部插入元素。

pop_back()：删除链表容器的最后一个元素。

remove ()：删除链表容器中所有指定值的元素。

remove_if(cmp)：删除链表容器中满足条件的元素。

erase()：从链表容器中删除一个或几个元素。

unique()：删除链表容器中相邻的重复元素。

clear()：删除链表容器中所有的元素。

insert(pos，elem)：在pos位置插入元素elem，即将元素elem插入到迭代器pos指定元素之前。

insert(pos，n，elem)：在pos位置插入n个元素elem。

insert(pos，pos1，pos2)：在迭代器pos处插入[pos1，pos2)的元素。

reverse()：反转链表。

sort()：对链表容器中的元素排序。

迭代器函数：begin()、end()、rbegin()、rend()。

关联容器

1）set（集合容器）/ multiset（多重集容器）
set和multiset都是集合类模板，其元素值称为关键字。set中元素的关键字是唯一的，multiset中元素的关键字可以不唯一，而且默认情况下会对元素按关键字自动进行升序排列。查找速度比较快，同时支持集合的交、差和并等一些集合上的运算，如果需要集合中的元素允许重复那么可以使用multiset。

set/multiset主要的成员函数

empty()：判断容器是否为空。

size()：返回容器中实际元素个数。

insert()：插入元素。

erase()：从容器删除一个或几个元素。

clear()：删除所有元素。

count(k)：返回容器中关键字k出现的次数。

find(k)：如果容器中存在关键字为k的元素，返回该元素的迭代器，否则返回end()值。

upper_bound()：返回一个迭代器，指向关键字大于k的第一个元素。

lower_bound()：返回一个迭代器，指向关键字不小于k的第一个元素。

迭代器函数：begin()、end()、rbegin()、rend()。

2）map（映射容器）/ multimap（多重映射容器）
map和multimap都是映射类模板。映射是实现关键字与值关系的存储结构，可以使用一个关键字key来访问相应的数据值value。在map/multimap中的key和value都是key类型，而key和value是一个pair类结构。
pair类结构的声明形如：

struct pair
{   T first;T second;
}

map/multimap利用pair的<运算符将所有元素即key-value对按key的升序排列，以红黑树的形式存储，可以根据key快速地找到与之对应的value（查找时间为O(log₂n)）。
map中不允许关键字重复出现，支持[]运算符；而multimap中允许关键字重复出现，但不支持[]运算符。

map/multimap主要的成员函数

empty()：判断容器是否为空。

size()：返回容器中实际元素个数。

map[key]：返回关键字为key的元素的引用，如果不存在这样的关键字，则以key作为关键字插入一个元素（不适合multimap）。

insert(elem)：插入一个元素elem并返回该元素的位置。

clear()：删除所有元素。

find()：在容器中查找元素。

count()：容器中指定关键字的元素个数（map中只有1或者0）。

迭代器函数：begin()、end()、rbegin()、rend()。

适配器容器

1）stack（栈容器）
它是一个栈类模板，和数据结构中的栈一样，具有后进先出的特点。栈容器默认的底层容器是deque。也可以指定其他底层容器。
例如，以下语句指定myst栈的底层容器为vector：

stack<string,vector<string> > myst;	//第2个参数指定底层容器为vector

stack主要的成员函数

empty()：判断栈容器是否为空。

size()：返回栈容器中实际元素个数。

push(elem)：元素elem进栈。

top()：返回栈顶元素。

pop()：元素出栈。

注意：stack容器没有begin()/end()和rbegin()/rend()这样的用于迭代器的成员函数。

2）queue（队列容器）
它是一个队列类模板，和数据结构中的队列一样，具有先进先出的特点，不允许顺序遍历。

queue主要的成员函数

empty()：判断队列容器是否为空。

size()：返回队列容器中实际元素个数。

front()：返回队头元素。

back()：返回队尾元素。

push(elem)：元素elem进队。

pop()：元素出队。

注意：queue容器没有begin()/end()和rbegin()/rend()这样的用于迭代器的成员函数。

3）priority_queue（优先队列容器）
它是一个优先队列类模板。优先队列是一种具有受限访问操作的存储结构，元素可以以任意顺序进入优先队列。一旦元素在优先队列容器中，出队操作将出队列最高优先级元素。

priority_queue主要的成员函数

empty()：判断优先队列容器是否为空。

size()：返回优先队列容器中实际元素个数。

push(elem)：元素elem进队。

top()：获取队头元素。

pop()：元素出队。

推荐书籍及网站

书籍

1）编程之美
2）编程珠玑（第二版）
3）算法之道
4）算法导论

网站

1）https://visualgo.net/en
2）https://www.cs.usfca.edu/~galles/visualization/Algorithms.html