数据结构MOOC | 0321 数据结构/算法-1.2

想了一想，emmmm还是接着写一点记录😊
虽然会额外消耗点时间，但我又不是为了赶进度哈哈。码字有点愉快而且方便回顾（OneNote贴代码的体验不大好诶 是我打开方式有误？）

比较循环和递归耗时

输出1～N
递归：在打印N前，先打印完1～N-1 空间复杂度递归调用栈 O(n) 时间O(n)
常规实现空间复杂度O(1) 时间O(n)

clock函数 头文件time.h

#include <cstdio>
#include <ctime>
clock_t start, stop;
double duration;
void PrintN(int N){
    for (int i = 1; i <= N; ++i) {
        printf("%d\n",i);
    }
}

void PrintN_re(int N){
    if(N){
        PrintN_re(N-1);
        printf("%d\n",N);
    }
}
int main() {
    printf("%d", CLOCKS_PER_SEC);
    start = clock();
    PrintN(260000);
    stop = clock();
    duration = (double)(stop-start)/CLOCKS_PER_SEC;

    start = clock();
    PrintN_re(260000); //最大栈深度差不多这个数？？？ 手动二分hhhhh
    stop = clock();
    printf("duration 1 : %lf sec\n", duration);
    duration = (double)(stop-start)/CLOCKS_PER_SEC;
    printf("duration 2 : %lf sec\n", duration);
    return 0;
}

比较不同实现耗时

• 计算多项式函数在定点处值
  加减远快于乘除，因此此处时间复杂度主要看乘除

#include <cstdio>
#include <ctime>
#include <cmath>

double data[1000] = {1.0};
double res1, res2;
clock_t start, stop;
double duration;

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

double f2(int n, const double a[], double x) {
    double p = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        p = x * p + a[i];
    }
    return p;
}

int main() {
//    printf("%d", CLOCKS_PER_SEC);
    for (int i = 1; i < 1000; ++i) {
        data[i] = data[i - 1] * 1.01;
    }
    start = clock();
    res1 = f1(1000, data, 1.0);
    stop = clock();
    duration = (double) (stop - start) / CLOCKS_PER_SEC;

    start = clock();
    res2 = f2(1000, data, 1.0);
    stop = clock();
    printf("res1 %lf  duration 1 : %lf sec\n", res1, duration);
    duration = (double) (stop - start) / CLOCKS_PER_SEC;
    printf("res2 %lf  duration 2 : %lf sec\n", res2, duration);
    return 0;
}

//        res1 2095815.563781  duration 1 : 0.000013 sec
//        res2 2095815.563781  duration 2 : 0.000004 sec

对运行时间小于一个tick的函数，可以跑多次（放进循环），测总时间。

最关心算法最坏情况复杂度（此外还有平均复杂度）