一、了解基本定义

1.算法定义

算法： 就是定义良好的计算过程该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。

比如排序问题的形式定义：
输入： n个数的一个序列<a1,a2,...,an>
输出： 输入序列 的一个排序<a1,a2,...,an> ,满足a1<=a2<=...an

2.数据结构

数据结构是存储和组织数据的一种方式，以便对数据迕行访问和修改。没有一种数据结构可以适用于所有用途和目的，因此了解数据结构的长处和局限性相当重要。

3.效率

衡量算法效率的常用标准是速度。

二、分析算法

1.分析算法

分析算法的结果意味着预测算法需要的资源。虽然有时候我们主要关心像内存、计算机硬件、通信带宽这类的硬件资源，但是通常我们想度量的是计算时间。一般来说，通过分析求解某个问题的几种候选算法，我们在其中选择一种最有效的算法。这种分析可能会指出不止一个的可行的候选算法，但是在这个过程中，我们往往可以抛弃几个较差的算法。

2.输入规模

输入规模的最佳概念依赖于研究的问题，对于许多问题，如排序或者计算离散傅里叶变换，最自然的量度就是通常的二进制记号表示输入所需的总位数。

3.运行时间

运行时间是指执行的基本操作或步数，定义‘步’的概念以便尽量独立于机器的，假定第i 行的每部执行所需时间为Ci,Ci是一个常量

比如下面是插入排序的一个伪代码模型，现在来该算法运行时间,其中A为一个数组,先不管算法如何实现

insert-sort(A) 　　　　　代价 　　　次数
for j=2 to A.length 　　　　1 　　　　 n
　key=A[j]　　　　　　　c2 　　　　n-1
　i=j-1　　　　　　 　　 c3 　　　　n-1
while i>0 and A[i]>key　　c4 　　　
　A[i+1]=A[i]　　　　　　c5 　 　 　
　i=i-1　　　　　　　　　c6 　　　
　A[i]=key　　　　　　　c7 　　　n-1

循环头次数会被循环体次数多1,多的一次为循环头发现不满足数据时，就退出了，导致了循环头比循环体多了1次

列出了代价和次数，接下来很容易能求得：
T(n)=c1n+c2(n−1)+c3(n−1)+c4+c5+c6+c7(n−1)

最好分析

当i取其值j-1时，有A[i]<=key ,那么条件不成立，那么对j = 2,3,...,n,有tj=1 是有最佳的运行时间,简单表示为：
　　　　　　　T(n)=an+b

最坏的情况

插入值必须和之前的每一个数比较过去， 即 while循环就一共就比较了j次（算最后循环的一次）
简化T(n)可以表示为：
　　　　　　　T(n)=+bn+c
因此他是n的二次函数

4.增长量级

我们使用某些简化的抽象来使算法分析的过程更加容易。我们真正感兴趣的运行时间的增长率或增长量级。所以我们只考虑公式中最重要的项（例如an^2）,当n很大时，低阶项相对于来说不太重要，我们也忽略了最重要项的常系数，因为对对大的输入，在确定计算效率时常量因子不如增长率重要。
对于插入排序，当我们忽视低阶项和最重要项的常系数时，只剩下最重要的项中的因子。

5.如何比较算法有效性

如果一个算法的最坏情况运行时间具有比另一个算法更低的增长量级，那么我们通常认为前者比后者更有效。
对于小的输入，有可能会有较高增量量级的运行快

三、渐近记号Θ、Ο、o、Ω、ω详解

1.渐近精确界记号：Θ（big-theta）

假设算法A的运行时间表达式T1(n)为：T1(n)=30+20+40+46n+100
假设算法B的运行时间表达式T2(n)为：T2(n)=1000+50+78n+10
当问题规模足够大的时候，例如n=100万，算法的运行时间将主要取决于时间表达式的第一项，其它项的执行时间只有它的几十万分之一，可以忽略不计。第一项的常数系数，随着n的增大，对算法的执行时间也变得不重要了。
  于是，算法A的运行时间可以记为：T1(n)≈n，记为T1(n)=Θ(n)；算法B的运行时间可以记为：T2(n)≈n，记为T2(n)=Θ(n)。

Θ的数学含义:
Θ(g(n))={f(n):存在正常量c1、c2和n₀，使得对所有n≥n₀，有0≤c1g(n)≤f(n)≤c2g(n)}若存在正常量c1、c2，使得对于足够大的n，函数f(n)能“夹入”c1g(n)与c2g(n)之间，则f(n)属于集合Θ(g(n))，记作f(n)∈Θ(g(n))。作为代替，我们通常记“f(n)=Θ(g(n))”。

由下图中左侧f(n)=Θ(g(n))图可以看出，对所有n>n₀时，函数f(n)乘一个常量因子可等于g(n)，我们称g(n)是f(n)的一个 渐近紧确界 。Θ记号在五个记号中，要求是最严格的，因为g(n)即可以表示上界也可以表示下界

渐近符号.png

需要注意的是：Θ(g(n))的定义要求每个成员f(n)∈Θ(g(n))均渐近非负，即当n足够大时，f(n)非负。 渐近正函数 就是对所有足够大的n均为正的函数。

2.渐近上界记号：O(big-oh)

定义：设f(n)和g(n)是定义域为自然数集N上的函数。若存在正数c和n₀，使得对一切n≥n₀都有0≤f(n)≤cg(n)成立，则称f(n)的渐进的上界是g(n)，记作f(n)=O(g(n))。通俗的说n满足一定条件范围内，函数f(n)的阶不高于函数g(n)。

根据符号O的定义，用它评估算法的复杂度得到的只是问题规模充分大时的一个上界。这个上界的阶越低，评估越精确，越有价值。

例如：设f(n)=+n,则
f(n)=O()，则 0≤+n≤c，求解取c=2,n₀=1即可 满足
f(n)=O()，则0≤+n≤c，取c=1,n₀=2即可。显然，O()作为上界更为精确。

几种常见的复杂度关系:

O(1)<O(logn)<O(n)<O(nlogn)<O()<O()<O(n!)<O()
需要注意的是：对数函数在没有底数时，默认底数为2；如lgn=logn=log2n因为计算机中很多程序是用二分法实现的。

3.渐近下界记号：Ω(big-omege)

定义：设f(n)和g(n)是定义域为自然数集N上的函数。若存在正数c和n₀，使得对一切n≥n₀都有0≤cg(n)≤f(n)成立，则称f(n)的渐进的下界是g(n)，记作f(n)=Ω(g(n))。通俗的说n满足一定条件范围内，函数f(n)的阶不低于函数g(n)。

根据符号Ω的定义，用它评估算法的复杂度得到的只是问题规模充分大时的一个下界。这个下界的阶越高，评估越精确，越有价值。

例如：设f(n)=+n,则
f(n)=Ω()，则 c≤+n，取c=1,n₀=1即可
f(n)=Ω(100n)，则 c100n ≤+n,取c=1/100 ,n0=1即可

显然，Ω()作为下界更为精确。

4.非渐近紧确上界：o(小-oh)

定义1：设f(n)和g(n)是定义域为自然数集N上的函数。若对于任意正数c，都存在n₀，使得对一切n≥n₀都有0≤f(n)<cg(n)成立，则称f(n)的渐进的非紧确上界是g(n)，记作f(n)=o(g(n))。通俗的说n满足一定条件范围内，函数f(n)的阶低于函数g(n)。

由O记号提供的渐近上界可能是渐近紧确的，也可能是非紧确的。（如：2=O()是渐近紧确的，而2n=O()是非紧确上界。）
例子：f(n)=+n，则f(n)=o()

5.非渐近紧确下界：ω(小-omege)

定义1：设f(n)和g(n)是定义域为自然数集N上的函数。若对于任意正数c，都存在n₀，使得对一切n≥n₀都有0≤cg(n)<f(n)成立，则称f(n)的渐进的非紧确下界是g(n)，记作f(n)=ω(g(n))。通俗的说n满足一定条件范围内，函数f(n)的阶高于函数g(n)。

ω记号与Ω的关系类似于o和O记号的关系。我们用ω表示一个非渐近紧确的下界。
例子：f(n)=+n，则f(n)=ω(n)是正确的。f(n)=ω()则是错误的，f(n)=Ω()是正确的。

6.渐近记号Θ、Ο、o、Ω、ω关系