时间复杂度

1算法复杂度

分为和。其作用： 是指执行算法所需要的计算工作量；而是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即）资源，因此复杂度分为时间和空间复杂度。）

2时间复杂度

时间频度

一个执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个花费的时间与算法中语句的执行次数，哪个算法中语句执行次数多，它花费时间就多。一个中的语句执行次数称为语句频度或时间频度。记为T(n)。

计算方法

1. 一般情况下，的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的记做：T(n)=O(f(n))

分析：随着模块n的增大，执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的越低，算法的效率越高。

2. 在计算的时候，先找出的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同（它的同数量级有以下：1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则T(n) = O(f(n))

例：算法：

1 2 3 4 5 6 7 8 9

for (i=1;i<=n;++i) {     for (j=1;j<=n;++j)     {         c[i][j]=0;     //该步骤属于基本操作 执行次数：n的平方 次         for (k=1;k<=n;++k)              c[i][j] += a[i][k]*b[k][j]; //该步骤属于基本操作 执行次数：n的三次方 次     } }

则有 T(n) = n 的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级

则有 f(n) = n的三次方，然后根据 T(n)/f(n) 求极限可得到常数c

则该的时间度：T(n) = O(n^3) 注：n^3即是n的3次方。

3.在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。

分类

按数量级递增排列，常见的有：

常数阶O(1),对数阶O(log2n),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述不断增大，的执行效率越低。

关于对其的理解

《数据结构（C语言版）》------严蔚敏 吴伟民编著 第15页有句话"整个算法的执行时间与基本操作重复执行的次数成正比。"

基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O(f(n))

如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间。

而该页对“语句频度”也有定义：指的是该语句重复执行的次数。

如果是基本操作所在语句重复执行的次数，那么就该是f(n)。

上边的n都表示的问题规模。

3空间复杂度

一个的是指运行完一个程序所需内存的大小。利用的，可以对程序的运行所需要的内存多少有个预先估计。一个执行时除了需要和存储本身所使用的指令、常数、和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。执行时所需包括以下两部分。

（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（、简单）等所占的空间。这部分属于静态空间。

（2）可变空间，这部分空间的主要包括动态分配的空间，以及栈所需的空间等。这部分的空间大小与有关。

一个所需的用f(n)表示。

S(n)=O(f(n))

其中n为问题的规模，S(n)表示。

大写O代表 　　在计算机科学上用来表示函数的级数，通常称为“大O符号”

	

		时间复杂度O(N)是什么？
	

	

		就是级别为n的。是的其中一种算法