算法概述（算法基础）_算法的基本流程

1.算法的概念

程序运行时需要的资源有两种
时间：程序运行需要的时间。
空间：程序运行需要的存储空间。

什么是算法

算法是求解问题的一系列计算步骤，用来将输入数据转换成输出结果 ：
输入---->算法---->输出
如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的。
算法设计应满足以下几条目标：
1.正确性
2.可使用性
3.可读性
4.健壮性
5.高效率与低存储量需求
算法具有以下5个重要特征：
1.有限性
2.确定性
3.可行性
4.输入性
5.输出性

算法和数据结构

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

算法设计的基本步骤

1.分析求解问题
2.选择数据结构和算法设计策略
3.描述算法
4.证明算法的正确性
5.算法分析

2.算法分析

算法分析是分析算法占用计算机资源的情况。
所以算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。

算法时间复杂度分析

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

bool Solve(double a[][MAX],int m,int n,double &s)
{
   int i; s=0;//顺序结构
   if (m!=n) return false;//分支结构
   for (i=0;i<m;i++)//循环结构
     s+=a[i][i];
   return true;//顺序结构
}

1
2
3
4
5
6
7
8
9

设n为算法中的问题规模，通常用大O、大Ω等两种渐进符号表示算法的执行时间与n之间的一种增长关系。

定义1（大O符号），f(n)=O(g(n))（读作“f(n)是g(n)的大O”）当且仅当存在正常量c和n0，使当n≥n0时，f(n)≤cg(n)，即g(n)为f(n)的上界.

如3n+2=O(n)，因为当n≥2时，3n+2≤4n。
10n2+4n+2=O(n4)，因为当n≥2时，10n2+4n+2≤10n4。

大O符号用来描述增长率的上界，表示f(n)的增长最多像g(n) 增长的那样快，也就是说，当输入规模为n时，算法消耗时间的最大值。这个上界的阶越低，结果就越有价值，所以，对于10n2+4n+2，O(n2)比O(n4) 有价值。
一个算法的时间用大O符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑上界”或“紧确上界”。

定义2（大Ω符号），f(n)=Ω(g(n))（读作“f(n)是g(n)的大Ω”）当且仅当存在正常量c和n0，使当n≥n0时，f(n)≥cg(n)，即g(n)为f(n)的下界。

如3n+2=Ω(n)，因为当n≥1时，3n+2≥3n。
10n2+4n+2=Ω(n2)，因为当n≥1时，10n2+4n+2≥n2。

大Ω符号用来描述增长率的下界，表示f(n)的增长最少像g(n) 增长的那样快，也就是说，当输入规模为n时，算法消耗时间的最小值。
与大O符号对称，这个下界的阶越高，结果就越有价值，所以，对于10n2+4n+2，Ω(n2)比Ω(n) 有价值。一个算法的时间用大Ω符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。

算法的最好情况是指算法在所有输入I下所执行基本语句的最少次数。
算法的最坏情况为是指算法在所有输入I下所执行基本语句的最大次数。

2.非递归算法时间复杂度分析

对于非递归算法，分析其时间复杂度相对比较简单，关键是求出代表算法执行时间的表达式。
　　通常是算法中基本语句的执行次数，是一个关于问题规模n的表达式，然后用渐进符号来表示这个表达式即得到算法的时间复杂度。
　　
3.递归算法的时间复杂度分析

递归算法是采用一种分而治之的方法，把一个“大问题”分解为若干个相似的“小问题”来求解。
　　对递归算法时间复杂度的分析，关键是根据递归过程建立递推关系式，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式即得到算法的时间复杂度。

算法空间复杂度分析

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

3.算法设计工具——STL

STL概述

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

什么是STL容器

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

为此，使用STL时必须将下面的语句插入到源代码文件开头：
using namespace std;
这样直接把程序代码定位到std命名空间中。

什么是STL算法

STL算法是用来操作容器中数据的模板函数，STL提供了大约100个实现算法的模版函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。
STL算法部分主要由头文件、和组成。

什么是STL迭代器

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

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

迭代器的常用运算如下：
++：正向移动迭代器。
–：反向移动迭代器。
*：返回迭代器所指的元素值。

常用的STL容器

顺序容器
适配器容器
关联容器

顺序容器

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

定义vector容器的几种方式如下：

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

vector提供了一系列的成员函数，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。
除了有字符串的一些常用操作以外，还有包含了所有的序列容器的操作。字符串的常用操作包括增加、删除、修改、查找比较、连接、输入、输出等。

创建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

常用的成员函数如下：

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 dq1; //定义元素为int的双端队列dq1 deque
dq2(10); //指定dq2的初始大小为10个int元素 deque dq3(10，1.23);
//指定dq3的10个初始元素的初值为1.23 deque 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 l1; //定义元素为int的链表l1 list l2
(10); //指定链表l2的初始大小为10个int元素 list l3
(10，1.23); //指定l3的10个初始元素的初值为1.23 list
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()。

说明：STL提供的sort()排序算法主要用于支持随机访问的容器，而list容器不支持随机访问，为此，list容器提供了sort()采用函数用于元素排序。类似的还有unique()、reverse()、merge()等STL算法。

关联容器

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。
在set/multiset中的key和value都是key类型，而key和value是一个pair类结构。
pair类结构的声明形如：

struct pair
{   T first;
    T second;
}

1
2
3
4
5

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

map/multimap的主要成员函数如下：

empty()：判断容器是否为空。
size()：返回容器中实际元素个数。
map[key]：返回关键字为key的元素的引用，如果不存在这样的关键字，则以key作为关键字插入一个元素（不适合multimap）。
insert(elem)：插入一个元素elem并返回该元素的位置。
clear()：删除所有元素。
find()：在容器中查找元素。
count()：容器中指定关键字的元素个数（map中只有1或者0）。
迭代器函数：begin()、end()、rbegin()、rend()。

在map中修改元素非常简单，这是因为map容器已经对[]运算符进行了重载。例如：

map<char,int> mymap;	
		   //定义map容器mymap，其元素类型为pair<char,int>
mymap['a'] = 1;   //或者mymap.insert(pair<char，int>('a',1) );
1
2
3

获得map中一个值的最简单方法如下：

  int ans = mymap['a'];
1

只有当map中有这个关键字（‘a’）时才会成功，否则会自动插入一个元素，值为初始化值。可以使用find() 方法来发现一个关键字是否存在。

适配器容器

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

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

stack容器主要的成员函数如下：

empty()：判断栈容器是否为空。
size()：返回栈容器中实际元素个数。
push(elem)：元素elem进栈。
top()：返回栈顶元素。 pop()：元素出栈。

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

2）queue（队列容器）
它是一个队列类模板，和数据结构中的队列一样，具有先进先出的特点。不允许顺序遍历，没有begin()/end()和rbegin()/rend()这样的用于迭代器的成员函数。
主要的成员函数如下：

empty()：判断队列容器是否为空。
size()：返回队列容器中实际元素个数。
front()：返回队头元素。
back()：返回队尾元素。
push(elem)：元素elem进队。
pop()：元素出队。

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

主要的成员函数如下：

empty()：判断优先队列容器是否为空。 size()：返回优先队列容器中实际元素个数。 push(elem)：元素elem进队。
top()：获取队头元素。 pop()：元素出队。

在算法设计中STL的应用

存放主数据

算法设计重要步骤是设计数据的存储结构，除非特别指定，程序员可以采用STL中的容器存放主数据，选择何种容器不仅要考虑数据的类型，还有考虑数据的处理过程。
例如，字符串可以采用string或者vector来存储，链表可以采用list来存储。

存放临时数据

在算法设计中，有时需要存放一些临时数据。通常的情况是，如果后存入的元素先处理，可以使用stack栈容器；
如果先存入的元素先处理，可以使用queue队列容器；如果元素处理顺序按某个优先级进行，可以使用priority_queue优先队列容器。

检测数据元素的唯一性

可以使用map容器或者哈希表容器检测数据元素是否唯一或者存放累计个数。

数据排序

对于list容器的元素排序可以使用其成员函数sort()，对于数组或者vector等具有随机访问特性的容器，可以使用STL算法sort()。
下面以STL算法sort()为例讨论：
1）内置数据类型的排序
对于内置数据类型的数据，sort()默认是以less（小于关系函数）作为关系函数实现递增排序。
为了实现递减排序，需要调用头文件中定义的greater类模板。
例如，以下程序使用greater()实现vector容器元素的递减排序（其中sort(myv.begin(),myv.end(),less())语句等同于sort(myv.begin(),myv.end())，实现默认的递增排序）：

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>			//包含less、greater等
using namespace std;
void Disp(vector<int> &myv)		//输出vector的元素
{  vector<int>::iterator it;
   for(it = myv.begin();it!=myv.end();it++)
	cout << *it << " ";
   cout << endl;
}
void main()
{  int a[]={2,1,5,4,3};
   int n=sizeof(a)/sizeof(a[0]);
   vector<int> myv(a,a+n);
   cout << "初始myv:  "; Disp(myv);	//输出：2 1 5 4 3
   sort(myv.begin(),myv.end(),less<int>());
   cout << "递增排序: "; Disp(myv);	//输出：1 2 3 4 5
   sort(myv.begin(),myv.end(),greater<int>());
   cout << "递减排序: "; Disp(myv);	//输出：5 4 3 2 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2）自定义数据类型的排序
对于自定义数据类型如结构体数据，同样默认是less（即小于关系函数）作为关系函数，但需要重载该函数。另外还可以自己定义关系函数()。在这些重载函数或者关系函数中指定数据的排序顺序（按哪些结构体成员排序，是递增还是递减）。
归纳起来，实现排序时主要有两种方式：

方式1：在声明结构体类型中重载<运算符，以实现按指定成员的递增或者递减排序。如sort(myv.begin(),myv.end())调用默认<运算符对myv容器的所有元素实现排序。
方式2：自己定义关系函数()，以实现按指定成员的递增或者递减排序。如sort(myv.begin(),myv.end(),Cmp())调用Cmp的()运算符对myv容器的所有元素实现排序。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
struct Stud
{  int no;
   string name;
   Stud(int no1,string name1)	//构造函数
   {	no=no1;
	name=name1;
   }
   bool operator<(const Stud &s) const	//方式1：重载<运算符
   {
	return s.no<no;   //用于按no递减排序，将<改为>则按no递增排序
   }
};
struct Cmp			//方式2：定义关系函数()
{  bool operator()(const Stud &s,const Stud &t) const
   {
	return s.name<t.name; 
		//用于按name递增排序，将<改为>则按name递减排序
   }
};
void Disp(vector<Stud> &myv)	//输出vector的元素
{   vector<Stud>::iterator it;
    for(it = myv.begin();it!=myv.end();it++)
	cout << it->no << "," << it->name << "\t";
    cout << endl;
}
void main()
{  Stud a[]={Stud(2,"Mary"),Stud(1,"John"),Stud(5,"Smith")};
   int n=sizeof(a)/sizeof(a[0]);
   vector<Stud> myv(a,a+n);
   cout << "初始myv:    "; Disp(myv);  
			//输出：2,Mary   1,John  5,Smith
   sort(myv.begin(),myv.end());	  //默认使用<运算符排序
   cout << "按no递减排序:   "; Disp(myv);	
			//输出：5,Smith  2,Mary  1,John
   sort(myv.begin(),myv.end(),Cmp());  //使用Cmp中的()运算符进行排序
   cout << "按name递增排序: "; Disp(myv);
			//输出：1,John   2,Mary  5,Smith
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

优先队列作为堆

在有些算法设计中用到堆，堆采用STL的优先队列来实现，优先级的高低由队列中数据元素的关系函数（比较运算符）确定，很多情况下需要重载关系函数。
1）元素为内置数据类型的堆
对于C/C++内置数据类型，默认是less（小于关系函数）作为关系函数，值越大优先级的越高（即大根堆），可以改为以greater作为关系函数，这样值越大优先级的越低（即小根堆）。
例如，以下程序中pq1为大根堆（默认），pq2为小根堆（通过greater实现）：
1）元素为内置数据类型的堆
对于C/C++内置数据类型，默认是less（小于关系函数）作为关系函数，值越大优先级的越高（即大根堆），可以改为以greater作为关系函数，这样值越大优先级的越低（即小根堆）。
例如，以下程序中pq1为大根堆（默认），pq2为小根堆（通过greater实现）：

 #include <iostream>
#include <queue>
using namespace std;
void main()
{  int a[]={3,6,1,5,4,2};
   int n=sizeof(a)/sizeof(a[0]);
   //(1)优先级队列pq1默认是使用vector作容器
   priority_queue<int> pq1(a,a+n);
   cout << "pq1: ";
   while (!pq1.empty())
   {	cout << pq1.top() << " ";	//while循环输出:6 5 4 3 2 1
	pq1.pop();
   }
   cout << endl;
   //(2)优先级队列pq2使用vector作容器,int元素的关系函数改为greater
   priority_queue<int,vector<int>,greater<int> > pq2(a,a+n);
   cout << "pq2: ";
   while (!pq2.empty())
   {	cout << pq2.top() << " ";	//while循环输出:1 2 3 4 5 6
	pq2.pop();
   }
   cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2）元素为自定义类型的堆
对于自定义数据类型如结构体数据，同样默认是less（即小于关系函数）作为关系函数，但需要重载该函数。
另外还可以自己定义关系函数()。在这些重载函数或者关系函数中指定数据的优先级（优先级取决于哪些结构体，是越大越优先还是越小越优先）。

#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Stud					//声明结构体Stud
{  int no;
   string name;
   Stud(int n,string na)			//构造函数
   {	no=n;
	name=na;
   }
   bool operator<(const Stud &s) const	//重载<关系函数
   {	return no<s.no;  }
   bool operator>(const Stud &s) const	//重载>关系函数
   {	return no>s.no;  }
};
//结构体的关系函数,改写operator()
struct StudCmp
{   bool operator()(const Stud &s,const Stud &t) const
    {
	return s.name<t.name;		//name越大越优先
    }
};

void main()
{  Stud a[]={Stud(2,"Mary"),Stud(1,"John"),Stud(5,"Smith")};
   int n=sizeof(a)/sizeof(a[0]);
   //(1)使用Stud结构体的<关系函数定义pq1
   priority_queue<Stud> pq1(a,a+n);
   cout << "pq1出队顺序: ";
   while (!pq1.empty())		//按no递减输出
   {	cout << "[" << pq1.top().no << "," << 
			pq1.top().name << "]\t";
	pq1.pop();
   }
   cout << endl;
   //(2)使用Stud结构体的>关系函数定义pq2
    priority_queue<Stud,deque<Stud>,greater<Stud> > pq2(a,a+n);
    cout << "pq2出队顺序: ";
    while (!pq2.empty())			//按no递增输出
    {	cout << "[" << pq2.top().no << "," << 
			pq2.top().name << "]\t";
	pq2.pop();
    }
    cout << endl;
    
//(3)使用结构体StudCmp的关系函数定义pq3
   priority_queue<Stud,deque<Stud>,StudCmp > pq3(a,a+n);
   cout << "pq3出队顺序: ";
   while (!pq3.empty())		//按name递减输出
   {	cout << "[" << pq3.top().no << "," 
			<< pq3.top().name << "]\t";
	pq3.pop();
   }
   cout << endl;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56