C语言的算法的时间与空间复杂度的求法

时间的复杂度是根据你的变量N运算次数决定

绥江ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为成都创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：028-86922220（备注：SSL证书合作）期待与您的合作！

例

for(int i = 0; i n;++i)

;

这个循环执行n次 所以时间复杂度是O(n)

for(int i = 0; i n;++i)

{

for(int j = 0; j n;++j)

;

}

这嵌套的两个循环 而且都执行n次

那么它的时间复杂度就是 O(n^2)

空间的复杂度是指程序执行对系统存储空间的占用情况衡量，是储存空间的大小和变换等等决定的。一般的递归算法就要有O(n)的空间复杂度了,简单说就是递归集算时通常是反复调用同一个方法，递归n次，就需要n个空间。由于现在的计算机的内存趋向于大容量，空间复杂度相对于时间复杂度来说就不那么重要了。

C语言：请列举一个以时间换空间或以空间换时间的例子，下面代码： 请帮忙解释一下空间和时间转换的原理？

第一个，用空间换时间，swap中定义了c，就是在内存中又开辟了一个int内存空间，然后一次swap需要进行三次赋值运算。

第二个，用时间换空间，swap中没有额外的定义变量，也就是没有内存的开辟。但是一共进行了3次加(减)法运算和三次赋值运算。运算次数比第一个多，所以时间效率低，但是没有开辟额外内存，所以空间效率高。

谁能帮我用C语言写一个测试选择排序性能（函数的运行时间）的程序，不胜感激！

如下定义clock_t变量start 和end start=clock();开始计时end=clock();结束计时，

printf("\ntime is %5.2f",difftime(end,start));输出。 注意头文件。

由于计算很快，数组维数太小 运行时间一般为0，取维数大一点才能计算出时间

不同机器上时间一般不同。

#includetime.h

#includeconio.h

#includedos.h

#includestdio.h

main()

{clock_t start,end; //计算时间

int a[10000];

int temp,min;

for(int i=0;i10000;i++) //数组赋值

a[i]=10000-i;

start=clock(); //开始

for(i=0;i10000;i++) //排序

{ for(int j=i+1;j10000;j++)

{if(a[i]=a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}}

}

end=clock();//结束计时

for(int m=0;m10000;m++)//输出

printf(" %d",a[m]);

printf("\ntime is %5.2f",difftime(end,start));//输出时间

getch();

}

C语言中怎样测试函数执行时间

有4种方法可以达成测算程序运行时间的目的。

它们分别是使用clock, times, gettimeofday, getrusage来实现的。

下面就来逐一介绍，并比较它们的优劣点。

系统测试环境：

VirtualBox (Ubuntu 9.10)

gcc version 4.4.1

libc6 2.10.1-0ubuntu16

Core Duo T2500 2GMHz

例程如下：

只要修改第11行的定义值，就可以使用不同的测量方法了。

#include sys/time.h

#include sys/resource.h

#include unistd.h

#include stdio.h

#include time.h

#define TEST_BY_CLOCK (char)(0x00)

#define TEST_BY_TIMES (char)(0x01)

#define TEST_BY_GETTIMEOFDAY (char)(0x02)

#define TEST_BY_GETRUSAGE (char)(0x03)

#define TEST_METHOD (TEST_BY_GETTIMEOFDAY)

#define COORDINATION_X (int)(1024)

#define COORDINATION_Y (int)(1024)

static int g_Matrix[COORDINATION_X][COORDINATION_Y];

double getTimeval()

{

struct rusage stRusage;

struct timeval stTimeval;

if (TEST_METHOD == TEST_BY_GETTIMEOFDAY)

{

gettimeofday(stTimeval, NULL);

}

else if (TEST_METHOD == TEST_BY_GETRUSAGE)

{

getrusage(RUSAGE_SELF, stRusage);

stTimeval = stRusage.ru_utime;

}

return stTimeval.tv_sec + (double)stTimeval.tv_usec*1E-6;

}

int main()

{

int i, j;

int n = 0;

clock_t clockT1, clockT2;

double doubleT1, doubleT2;

if (TEST_METHOD == TEST_BY_CLOCK)

{

clockT1 = clock();

}

else if (TEST_METHOD == TEST_BY_TIMES)

{

times(clockT1);

}

else if (TEST_METHOD == TEST_BY_GETTIMEOFDAY)

{

doubleT1 = getTimeval();

}

else if (TEST_METHOD == TEST_BY_GETRUSAGE)

{

doubleT1 = getTimeval();

}

for (i = 0; i COORDINATION_X; i++)

{

for (j = 0; j COORDINATION_Y; j++)

{

g_Matrix[i][j] = i * j;

}

}

if (TEST_METHOD == TEST_BY_CLOCK)

{

clockT2 = clock();

printf("Time result tested by clock = %10.30f\n",(double)(clockT2 - clockT1)/CLOCKS_PER_SEC);

}

else if (TEST_METHOD == TEST_BY_TIMES)

{

times(clockT2);

printf("Time result tested by times = %10.30f\n", (double)(clockT2 - clockT1)/sysconf(_SC_CLK_TCK));

}

else if (TEST_METHOD == TEST_BY_GETTIMEOFDAY)

{

doubleT2 = getTimeval();

printf("Time result tested by gettimeofday = %10.30f\n",(double)(doubleT2 - doubleT1));

}

else if (TEST_METHOD == TEST_BY_GETRUSAGE)

{

doubleT2 = getTimeval();

printf("Time result tested by getrusage = %10.70f\n", (double)(doubleT2 - doubleT1));

}

return 0;

}

1. 使用clock的方法：

clock是ANSI C的标准库函数，关于这个函数需要说明几点。

首先，它返回的是CPU耗费在本程序上的时间。也就是说，途中sleep的话，由于CPU资源被释放，那段时间将不被计算在内。

其次，得到的返回值其实就是耗费在本程序上的CPU时间片的数量，也就是Clock Tick的值。该值必须除以CLOCKS_PER_SEC这个宏值，才

能最后得到ss.mmnn格式的运行时间。在POSIX兼容系统中，CLOCKS_PER_SEC的值为1,000,000的，也就是

1MHz。

最后，使用这个函数能达到的精度大约为10ms。

2. 使用times的方法：

times的用法基本和clock类似，同样是取得CPU时间片的数量，所不同的是要除以的时间单位值为sysconf(_SC_CLK_TCK)。

3. 使用gettimeofday的方法：

用gettimeofday直接提取硬件时钟进行运算，得到的结果的精度相比前两种方法提高了很多。

但是也正由于它提取硬件时钟的原因，这个方法只能计算程序开始时间和结束时间的差值。而此时系统中如果在运行其他的后台程序，可能会影响到最终结果的值。如果后台繁忙，系统dispatch过多的话，并不能完全真实反映被测量函数的运行时间。

4. 使用getrusage的方法:

getrusage得到的是程序对系统资源的占用信息。只要指定了RUSAGE_SELF，就可以得到程序本身运行所占用的系统时间。

c语言怎么测试一段程序的运行时间？

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)   //CLOCKS_PER_SEC为系统自定义的

可以看到每过千分之一秒（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( ) 

{

long i = 10000000L;

clock_t start, finish;

double Total_time;

/* 测量一个事件持续的时间*/

printf( "Time to do %ld empty loops is ", i );

start = clock();

while( i--) ;

finish = clock();

Total_time = (double)(finish-start) / CLOCKS_PER_SEC;

printf( "%f seconds/n", Total_time);

return 0;

}

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

Time to do 10000000 empty loops is 0.03000 seconds

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

参考资料

c语言测试程序执行时间.csdn博客[引用时间2017-12-31]

C语言里面怎样测出程序运算的时间?

#include time.h

#include stdio.h

int main()

{

//...

double Times = clock() / (double)(CLOCKS_PER_SEC);

printf("%.2lf\n",Times);

//...

return 0;

}

简单地说，就是使用time.h库中的clock()函数。

具体讲，程序中的clock()函数在time.h中声明，每次调用它，返回程序自开始运行至此经历的时间，单位是(1/CLOCKS_PER_SEC)秒，CLOCKS_PER_SEC是在time.h中声明的一个常数，在Windows环境下，它的值是1000，也就是说若程序执行了1.5s,调用clock()函数会返回1500;在Linux或Unix环境下，它的值是1000000，即此时clock()函数会返回1500000，为了增强程序的可移植性，故通用写法为clock() / (double)(CLOCKS_PER_SEC)。

文章名称：c语言测试函数时间与空间 用c语言求时间差
文章位置：http://hbruida.cn/article/dodcpis.html