一、算法

1、概念

• 对特定问题求解的一种描述，是一个指定的、有序的序列（也就是说如何解答这个问题，第一步、第二步、第三步分别怎么做......）；
• 也可以简单理解为一个有序的指令序列用来求解一个特定的问题；

2、算法的5个特性

• 有穷性：一个算法必须在有穷的时间之内完成；也就是求解的步骤是有限的，完成每一步的时间是有限的。
• 可行性：一个算法是可行的；也就是针对特定问题的求解，能够在有限步，有限时间内完成。
• 确定性：在算法中的指令序列，每一个指令都有确定的含义，不存在二义性。同一个条件里执行多次得到的结果都会是相同的输出。
• 输入：一个算法可以有0~n个输入。
• 输出一个算法一定有1~n个输出。

二、伪代码

1、概念

• 介于自然语言和程序语言之间的，对算法实现的一种表现形式。

2、举例说明

三、复杂度

1、分类

• 时间复杂度（考试重点）
• 空间复杂度

2、时间复杂度

（1）概念

• 是指程序从运行开始到结束所需要的时间。

（2）分析时间复杂度的方法

• 从算法中取一种对于所研究问题来说基本的运算操作，以该操作的重复次数作为运算的时间度量。
• 就是说在算法中看这个操作的重复程度叫做时间复杂度。

（3）举例说明时间复杂度

• 例如1：下面的每条语句都只操作一遍，程序就运行结束了，那么该程序的时间复杂度就是O(1);

• 例如2：for循环执行n次后才结束，所以这个程序的时间复杂度是O(n)。

• 例如3：嵌套循环语句，因为i<n、j<n，所以c=c+1会循环n的平方次，所以这个程序的时间复杂度是O(n的平方)。

（4）三种记作方法

• O（常考）
  • 上界，表示小于等于。
  • 定义一个函数g(n),O(g(n))表示对于f(n)存在一个正常数c和n，使得n>n0的时候，f(n)<=cg(n)，也就是0<=f(n)<=cg(n)，也就是说cg(n)是f(n)的上界。
  • 
• Ω
  • 下界，表示大于等于。
  • 定义一个函数g(n),Ω(g(n))表示对于f(n)存在一个正常数c和n，使得n>n0的时候，f(n)>=cg(n)，也就是f(n)>=cg(n)>=0，也就是说cg(n)是f(n)的下界。
  • 
• Θ
  • 紧致界。
  • 定义一个函数g(n),Θ(g(n))表示对于f(n)存在两个正常数c1和c2(c2>c1)，以及n，使得n>n0的时候，c2g(n)>=f(n)>=c1g(n)，也就是说（c1g(n)，c2g(n)）是f(n)的紧致界。
  • 

（5）排序（常考）

3、空间复杂度

（1）概念

• 指的是程序在运行过程中，需要临时占用存储空间大小的度量。
• 一般来讲空间复杂度只考虑在运行过程中，给局部变量分配的存储空间的大小。