算法的时间复杂度和空间复杂度

算法时间复杂度和空间复杂度

如何评估算法时间开销：
让算法先运行，事后统计运行时间？【存在问题：和机器性能有关；和编程语言有关，越高级的语言执行效率越低；和编译程序产生的机器指令质量有关；有些算法是不能事后再统计的(导弹控制算法)】

算法时间复杂度：事前预估算法时间开销T(n)与问题规模n的关系
1）最坏时间复杂度
2）平均时间复杂度
3）最好时间复杂度

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

测试算法效率(时钟打点)

问题：

源代码：

//clock():捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”
//常数CLK_TCK:机器时钟每秒所走的时钟打点数

//让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可

#include<stdio.h>
#include<time.h>
#include<math.h>

#define MAXN 10
#define MAXK 1e7//被测函数最大重复调用次数

clock_t start,stop;//clock_t是clock()函数返回的变量类型
double duration;//记录被测函数运行时间，以秒为单位

double f1(int n,double a[],double x){
    int i;
    double p=a[0];
    for(i=1;i<=n;i++){
        p += (a[i]*pow(x,i));
    }
    return p;

}
double f2(int n,double a[],double x){
    int i;
    double p=a[0];
    for(i=1;i<=n;i++){
        p+=(a[i]*pow(x,i));
    }
    return p;
}

int main(){
    int i,CLK_TCK;
    double a[MAXN];//存储多项式的系数
    for(i=0;i<MAXN;i++){
        a[i]=(double)i;
    }
    
    //不在测试范围内的准备工作写在clock()调用之前
    
    start=clock();//开始计时
    for(i=0;i<MAXK;i++){
        f1(MAXN-1,a,1.1);//把被测函数加在这里
    }
    stop=clock();//停止计时
    duration=((double)(stop-start))/CLK_TCK/MAXK;//计算函数单次运行时间
    printf("ticks1=%f\n",(double)(stop-start));
    printf("duration1=%6.2e\n",duration);
    
    //其他不在测试范围的处理写在后面，例如输出duration的值
    
    start=clock();//开始计时
    for(i=0;i<MAXK;i++){
        f2(MAXN-1,a,1.1);//把被测函数加在这里
    }
    stop=clock();//停止计时
    duration=((double)(stop-start))/CLK_TCK/MAXK;//计算函数单次运行时间
    printf("ticks2=%f\n",(double)(stop-start));
    printf("duration2=%6.2e\n",duration);
    return 0;
}