时间空间复杂度

算法的定义

对特定问题求解方法和步骤的一种描述，他是指令的有序序列。其中每个指令表示一个或多个操作。

算法与程序

算法是解决问题的一种或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。

程序是用某种程序设计语言对算法的具体实现。

算法的特性

有穷性：一个算法必须总是在执行又穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一一条执行路径，即对于相同的输入只能得到相同的输出。

可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

输入：一个算法有零个或多个输入。

算法设计和要求

可读性(Correctness)

可读性(Readability)

健壮性(Robustness)

高效性(Efficeincy)

算法和算法分析

一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。

算法的效率以下两个方面来考虑：

1.时间效率：指的是算法耗费的时间

2.空间效率：指的是算法执行过程中锁耗费的存储空间。

算法时间效率的度量

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗时间来度量。

两种方法

事后统计

将算法实现，测算其时间和空间开销。

事前分析

对算法所消耗资源的一种估算方法。

事前分析方法

一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作(如赋值，比较，移动等)所需的时间与算法中进行简单操作次数的乘积。

算法运行时间=一个简单操作所需的时间*见到操作次数

为了便于比较不同算法的时间复杂度，我们仅比较它们的数量级

若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)和T(n)是同数量级。记作T(n)=O(f(n))，称o(f(n))为算法的渐进时间复杂度(O是数量级的符号)，简称时间复杂度。

一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T(n)表示。

分析算法时间复杂度的基本方法

1.找出语句频度最大的那条语句作为基本语句

2.计算基本语句的频度得到问题规模n的某个函数f(n)

3.取其数量级用符号"O"表示

最坏时间复杂度：指在最坏情况下，算法的时间复杂度。

平均时间复杂度：指在所有可能输入实力在等概率出现的情况下，算法期望运行时间。

对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度：

a) 加法规则

$T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$

b) 乘法法则

$T(n)=T1(n)\ast T2(n)=O(f(n))\ast O(g(n))=O(f(n)\ast g(n))$

空间复杂度：算法所需存储空间的度量，

记作：S(n) = O(f(n))

其中n为问题的规模(或大小)

算法要占据的空间

算法本身要占据的空间，输入/输出，指令，常数，变量等

算法要使用的辅助空间

抽象数据类型=数据的逻辑结构+抽象运算(运算的功能描述)