a算法时间复杂度

1. 数据结构中排序和查找各种时间复杂度

数据结构中排序和查找各种时间复杂度
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的。…… 例子说明好多了。序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了， 所以选择排序不稳定的排序算法
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。所以插入排序是稳定的。
(4)快速排序
快速排序有两个方向，左边的i下标一直往右走（往后），当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走（往前），当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法。（不稳定发生在中枢元素和a[j]交换的时刻）
(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以，归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法
一、排序
排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
Shell O(nlogn) O(ns) 1<s<2 不稳定???="" o(1)???????="" s是所选分组</s
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)，R是基数(个十百)
二、查找
未写……
三 树图
克鲁斯卡尔算法的时间复杂度为O（eloge）
普里姆算法的时间复杂度为O（n2）
迪杰斯特拉算法的时间复杂度为O（n2）
拓扑排序算法的时间复杂度为O（n+e）
关键路径算法的时间复杂度为O（n+e）

2. 时间复杂度怎么计算

1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））
分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。
2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））
例：算法：
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. 算法复杂度的时间复杂度

（1）时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。
（2）时间复杂度
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
算法的时间性能分析
（1）算法耗费的时间和语句频度
一个算法所耗费的时间=算法中每条语句的执行时间之和
每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间
算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。
若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。
求两个n阶方阵的乘积 C=A×B,其算法如下:
# define n 100 // n 可根据需要定义,这里假定为100
void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
{ //右边列为各语句的频度
int i ,j ,k;
(1) for(i=0; i<n;i++) n+1
(2) for (j=0;j<n;j++) { n(n+1)
(3) C[i][j]=0; n2
(4) for (k=0; k<n; k++) n2(n+1)
(5) C[i][j]=C[i][j]+A[i][k]*B[k][j];n3
}
}
该算法中所有语句的频度之和(即算法的时间耗费)为：
T(n)=2n3+3n2+2n+1 (1.1)
分析：
语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。
算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。
（2）问题规模和算法的时间复杂度
算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。
矩阵乘积问题的规模是矩阵的阶数。
一个图论问题的规模则是图中的顶点数或边数。
一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。
算法MatrixMultiply的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有T(n)~O(n^3);
这表明，当n充分大时，T(n)和n^3之比是一个不等于零的常数。即T(n)和n^3是同阶的，或者说T(n)和n^3的数量级相同。记作T(n)=O(n^3)是算法MatrixMultiply的渐近时间复杂度。
（3）渐进时间复杂度评价算法时间性能
主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。
算法MatrixMultiply的时间复杂度一般为T(n)=O(n^3)，f(n)=n^3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。
交换i和j的内容。
Temp=i;
i=j;
j=temp;
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：
(1) x=0;y=0;
(2) for(k-1;k<=n;k++)
(3) x++;
(4) for(i=1;i<=n;i++)
(5) for(j=1;j<=n;j++)
(6) y++;
一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n^2，所以该程序段的时间复杂度为T(n)=O(n^2)。
当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
变量计数之二：
(1) x=1;
(2) for(i=1;i<=n;i++)
(3) for(j=1;j<=i;j++)
(4) for(k=1;k<=j;k++)
(5) x++;
该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：
则该程序段的时间复杂度为T(n)=O(n^3/6+低次项)=O(n^3)。
（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。
在数值A[0..n-1]中查找给定值K的算法大致如下：
(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3) i--;
(4)return i;
此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:
①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；
②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

4. 如何计算时间复杂度

1、先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。

2、举例

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的三次方）

),线性阶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都表示的问题规模。

5. 请问算法的时间复杂度是怎么计算出来的

首先假设任意一个简单运算的时间都是1，例如a=1;a++;a=a*b;这些运算的时间都是1.

那么例如
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
a++; //注意，这里计算一次的时间是1.
}
那么上面的这个例子的时间复杂度就是 m*n

再例如冒泡排序的时间复杂度是N*N；快排的时间复杂度是log(n)。

详细的情况，建议你看《算法导论》，里面有一章节，具体讲这个的。

6. 算法时间复杂度怎么算

一、概念
时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)
比如：一般总运算次数表达式类似于这样：
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a ！ =0时，时间复杂度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此类推
eg:
(1) for(i=1;i<=n;i++) //循环了n*n次，当然是O(n^2)
for(j=1;j<=n;j++)
s++;
(2) for(i=1;i<=n;i++)//循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)
for(j=i;j<=n;j++)
s++;
(3) for(i=1;i<=n;i++)//循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)
for(j=1;j<=i;j++)
s++;
(4) i=1;k=0;
while(i<=n-1){
k+=10*i; i++; }//循环了n-1≈n次，所以是O(n)(5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
//循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3，不考虑系数，自然是O(n^3)
另外，在时间复杂度中，log(2,n)(以2为底)与lg(n)(以10为底)是等价的，因为对数换底公式：
log(a,b)=log(c,b)/log(c,a)
所以，log(2,n)=log(2,10)*lg(n),忽略掉系数，二者当然是等价的
二、计算方法1.一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
2.一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））。随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。
在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。
3.常见的时间复杂度
按数量级递增排列，常见的时间复杂度有：
常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2)， 立方阶O(n^3),...， k次方阶O(n^k), 指数阶O(2^n) 。
其中，1.O(n)，O(n^2)， 立方阶O(n^3),...， k次方阶O(n^k) 为多项式阶时间复杂度，分别称为一阶时间复杂度，二阶时间复杂度。。。。2.O(2^n)，指数阶时间复杂度，该种不实用3.对数阶O(log2n), 线性对数阶O(nlog2n)，除了常数阶以外，该种效率最高
例：算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n^2
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n^3
}
}
则有 T（n）= n^2+n^3，根据上面括号里的同数量级，我们可以确定 n^3为T（n）的同数量级
则有f（n）= n^3，然后根据T（n）/f（n）求极限可得到常数c
则该算法的 时间复杂度：T（n）=O（n^3)
四、

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数
T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“大O记法”：在这种描述中使用的基本参数是
n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1.
交换i和j的内容
sum=0；（一次）
for(i=1;i<=n;i++)（n次 ）
for(j=1;j<=n;j++)
（n^2次 ）
sum++；（n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i<n;i++)
{
y=y+1;①
for
(j=0;j<=(2*n);j++)
x++;②
}
解：
语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1;①
for
(i=1;i<=n;i++) ②
{
s=a+b;③
b=a;④
a=s;⑤
}
解：语句1的频度：2,
语句2的频度：
n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n
)

2.4.
i=1;①
while (i<=n)
i=i*2; ②
解： 语句1的频度是1,
设语句2的频度是f(n),则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)=
log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：当i=m,
j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).


我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最
坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：


访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对
元素相乘并加到一起，所有元素的个数是n^2。
指数时间算法通常来源于需要求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如着名的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。

7. A*算法的时间复杂度是多少

从数学上定义，给定算法A，如果存在函数F(n)，当n=k时，F(k)表示算法A在输入规模为k的情况下的运行时间，则称F(n)为算法A的时间复杂度。这里首先要明确输入规模的概念。关于输入规模，不是很好下定义，非严格的讲，输入规模是指算法A所接受输入的自然独立体的大小。例如，对于排序算法来说，输入规模一般就是待排序元素的个数，而对于求两个同型方阵乘积的算法，输入规模可以看作是单个方阵的维数。为了简单起见，总是假设算法的输入规模是用大于零的整数表示的，即n=1,2,3,……,k,…… 对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为了解决这个问题，做以下两个说明： 1.忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。 2.对于输入特性的差异，将从数学上进行精确分析并带入函数解析式。

8. (11) 算法的时间复杂度是指______。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所

（11）[答案]C
[考点]数据结构与算法
[评析]
算法的复杂度分时间复杂度和空间复杂度。
时间复杂度：在运行算法时所耗费的时间为f(n)(即 n的函数)。
空间复杂度：实现算法所占用的空间为g(n)（也为n的函数）。
称O(f(n))和O(g(n))为该算法的复杂度。
简单的例子比如常见的顺序结构时间复杂度为O(1),1层循环里面次数为n，时间复杂度就是O(n),2层循环for i=1 to n,for j=1 to n算法时间复杂度为O(n2)（里面为n的平方），复杂度主要用于算法的效率比较与优化，比如排序，查找…

9. 求最短路径的A*算法的时间复杂度与空间复杂度是多少

从数学上定义，给定算法A，如果存在函数F(n)，当n=k时，F(k)表示算法A在输入规模为k的情况下的运行时间，则称F(n)为算法A的时间复杂度。这里首先要明确输入规模的概念。关于输入规模，不是很好下定义，非严格的讲，输入规模是指算法A所接受输入的自然独立体的大小。例如，对于排序算法来说，输入规模一般就是待排序元素的个数，而对于求两个同型方阵乘积的算法，输入规模可以看作是单个方阵的维数。为了简单起见，总是假设算法的输入规模是用大于零的整数表示的，即n=1,2,3,……,k,…… 对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为了解决这个问题，做以下两个说明： 1.忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。 2.对于输入特性的差异，将从数学上进行精确分析并带入函数解析式。