@Dmaxiya 2022-02-12T20:42:31.000000Z 字数 2273 阅读 1076

2022 春节寒假最后一次培训

Hello_World

时间复杂度的计算*

简介

运行时间计算方式： $\frac{程序计算次数}{10^8}s$
如：对 $1$ ~ $10^9$ 进行求和，若使用如下代码：

long long sum = 0, i;
for(i = 1; i <= 1000000000LL; ++i) {
    sum += i;
}

则程序执行的次数为 $10^9$ ，需要 10s，若使用如下代码：

long long sum = (1 + 1000000000LL) * 1000000000LL / 2;

则程序执行的次数为 $1$ ，所需要时间为 $10^{-8}s$ 。
实际代码的运行时间可能少于估计值，但大多数题目的数据都能保证：若程序运行次数超过 $10^8$ 必然返回超时。

练习

计算以下题目的时间复杂度：

习题讲解

高精度计算

加法

参考题目：P1601 A+B Problem（高精）
参考代码：https://www.luogu.com.cn/paste/e237i3pn

int add(int *a, int lena, int *b, int lenb, int *c) {
    int s = 0;
    int len = max(lena, lenb);
    for (int i = 0; i < len; ++i) {
        c[i] = s + a[i] + b[i];
        s = c[i] / 10;
        c[i] %= 10;
    }
    if (s != 0) {
        c[len++] = s;
    }
    return len;
}

减法

int sub(int *a, int lena, int *b, int lenb, int *c) {
    int s = 0;
    int aa, bb;
    int len = max(lena, lenb);
    for(int i = 0; i < len; ++i) {
        aa = a[i];
        if(i >= lenb) {
            bb = 0;
        } else {
            bb = b[i];
        }
        c[i] = (aa - bb - s + 10) % 10;
        if(aa < bb + s) {
            s = 1;
        } else {
            s = 0;
        }
    }
    for (int i = maxn - 1; i >= 0; --i) {
        if (c[i] != 0) {
            return i + 1;
        }
    }
    return 1;
}

乘法

参考题目：P1045 [NOIP2003 普及组] 麦森数
参考代码：https://www.luogu.com.cn/paste/dyv59ovw

int mult(int *a, int lena, int *b, int lenb, int *c) {
    for (int i = 0; i < lena; ++i) {
        for (int j = 0; j < lenb; ++j) {
            c[i + j] += a[i] * b[j];
        }
    }
    int cc = 0;
    for (int i = 0; i < lena + lenb; ++i) {
        c[i] += cc;
        cc = c[i] / 10;
        c[i] %= 10;
    }
    int idx = lena + lenb;
    while (cc != 0) {
        c[idx++] = cc % 10;
        cc /= 10;
    }
    for (int i = maxn - 1; i >= 0; --i) {
        if (c[i] != 0) {
            return i + 1;
        }
    }
    return 1;
}