算法执行所需操作时间

1. 算法的时间复杂度是指什么

算法的时间复杂度是指：执行程序所需的时间。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近无穷大时。

T(n)/f(n)的极限值为不等于零的常数，则称为f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。比如：

在 T(n)=4nn-2n+2 中，就有f(n)=nn，使得T(n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n*n)。

时间复杂度中大O阶推导是：

推导大O阶就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。

有条理的说，推导大O阶，按照下面的三个规则来推导，得到的结果就是大O表示法：运行时间中所有的加减法常数用常数1代替。只保留最高阶项去除最高项常数。

其他常见复杂度是：

f(n)=nlogn时，时间复杂度为O(nlogn)，可以称为nlogn阶。

f(n)=n³时，时间复杂度为O(n³)，可以称为立方阶。

f(n)=2ⁿ时，时间复杂度为O(2ⁿ)，可以称为指数阶。

f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。

f(n)=(√n时，时间复杂度为O(√n)，可以称为平方根阶。

2. C语言算法的时间复杂度如何计算啊

看看这个
每个循环都和上一层循环的参数有关。
所以要用地推公式：
设i(n)表示第一层循环的i为n时的循环次数，注意到他的下一层循环次数刚好就是n，分别是0,1,2...n-1
所以，把每一层循环设一个函数分别为：j(n),k(n),t(n)
则有
i(n)=j(0)+...+j(n-1)
j(n)=k(0)+...+k(n-1)
k(n)=t(0)+...+t(n-1)
i(0)=j(0)=k(0)=0
t(n)=1
而总循环数是i(0)+i(1)...+i(n-1)
可以根据递推条件得出准确值
所以算法复杂度是O(i(0)+i(1)...+i(n-1))
记得采纳啊

3. 影响算法执行时间的因素主要有哪些

影响算法执行时间的因素包括：

1、算法本身选用的策略；

2、问题的规模；

3、书写程序的语言；

4、编译产生的机器代码质量；

5、机器执行指令的速度等。

为便于比较算法本身的优劣，应排除其它影响算法效率的因素。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量。

(3)算法执行所需操作时间扩展阅读：

缩短算法时间的方法：

1、选择合理的存储结构。

数据的存储结构，分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

2、使用直接初始化。

与直接初始化对应的是复制初始化。

3、减少除法运算的使用。

无论是整数还是浮点数运算，除法都是一件运算速度很慢的指令，在计算机中实现除法是比较复杂的。所以要减少除法运算的次数。

4. 算法执行时间是指执行一次基本操作所需的时间吗

算法的执行时间仅仅指程序在进行该算法相关计算时所用的时间之和，一般不用算法执行时间描述算法的好坏，因为算法的执行时间取决于数据的大小和数量，一般要用时间复杂度来描述一个算法。

5. 一个算法的运行时所消耗的时间是如何测出来的

在忽略机器性能的基础上我们用算法时间复杂度来计算算法执行的时间
1.时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
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.分类
按数量级递增排列，常见的时间复杂度有： 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

6. C语言怎样统计一个算法执行的CPU时间

C/C++中的计时函数是clock()，而与其相关的数据类型是clock_t。在MSDN中，查得对clock函数定义如下：

clock_t clock( void );

这个函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元（clock tick）数，在MSDN中称之为挂钟时间（wal-clock）。其中clock_t是用来保存时间的数据类型，在time.h文件中，我们可以找到对它的定义：

#ifndef _CLOCK_T_DEFINED
typedef long clock_t;
#define _CLOCK_T_DEFINED
#endif

很明显，clock_t是一个长整形数。在time.h文件中，还定义了一个常量CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元，其定义如下：

#define CLOCKS_PER_SEC ((clock_t)1000)

可以看到每过千分之一秒（1毫秒），调用clock（）函数返回的值就加1。下面举个例子，你可以使用公式clock()/CLOCKS_PER_SEC来计算一个进程自身的运行时间：

void elapsed_time()
{
printf("Elapsed time:%u secs.\n",clock()/CLOCKS_PER_SEC);
}

当然，你也可以用clock函数来计算你的机器运行一个循环或者处理其它事件到底花了多少时间：

#include “stdio.h”
#include “stdlib.h”
#include “time.h”

int main( void )
{
long i = 10000000L;
clock_t start, finish;
double ration;
/* 测量一个事件持续的时间*/
printf( "Time to do %ld empty loops is ", i );
start = clock();
while( i-- ) ;
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "%f seconds\n", ration );
system("pause");
}

在笔者的机器上，运行结果如下：

Time to do 10000000 empty loops is 0.03000 seconds

上面我们看到时钟计时单元的长度为1毫秒，那么计时的精度也为1毫秒，那么我们可不可以通过改变CLOCKS_PER_SEC的定义，通过把它定义的大一些，从而使计时精度更高呢？通过尝试，你会发现这样是不行的。在标准C/C++中，最小的计时单位是一毫秒。

7. 计算机执行一条指令需要多长时间如何计算

计算机中时钟周期是（主频的倒数），一个时钟周期cpu仅完成一个最基本的动作，完成一个基本操作的时间为机器周期，一般由几个时钟周期组成；完成一条指令为指令周期。一般由几个机器周期组成，指令不同机器周期数也不同。
以我的本本1.6G 为例 ，机器周期由两个时钟周期组成，平均三个机器周期完成一条指令（这要假设，我看不到）
时钟周期为1/(1.6*1024m)=0.61ns 机器周期为0.61*2=1.22ns
平均指令周期3*1.22ns=3.66ns
平均指令执行速度为1/(3.66ns)=273.22MIPS(百万条指令每秒）
这只是计算方法，条件也是假设的，晶振我不知。
大致算法就这样，我数学不好。如有算错请多指教！