交付：一份完整的复杂度分析

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

这是这条路线的最终作品。前四步的函数已经合在一起，还差两处关键逻辑：pick 的边界判断、three_cases 的平均情况。补全后一次验完五条：「两两比较」n=5 时 10 次；翻倍后 4 倍；空间 5/0；n=m=1000 选「暴力」；线性查找最好/最坏/平均是 1/5/3。五条全过输出 验收通过，否则输出 验收失败。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步：据此选一个 n 为三千时立方要跑多久 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long count_pairs(long long n) {
    long long ops = 0;
    for (long long i = 0; i < n; i++)
        for (long long j = i + 1; j < n; j++) ops++;
    return ops;
}

long long brute_ops(long long n, long long m) { return n * m; }
long long prefix_ops(long long n, long long m) { return n + m; }

int lsearch_steps(const vector<int>& a, int target) {
    int steps = 0;
    for (int x : a) {
        steps++;
        if (x == target) return steps;
    }
    return steps;
}

long long grow(long long n) { return count_pairs(2 * n) / count_pairs(n); }

string space(const vector<int>& a) { return to_string(a.size()) + "/0"; }

string pick(long long n, long long m) {
    // TODO: 暴力操作数超过一百万就返回 前缀和，否则返回 暴力
    (void)n; (void)m;
    return "";
}

string three_cases(const vector<int>& a) {
    int best = lsearch_steps(a, a.front());
    int worst = lsearch_steps(a, a.back());
    int total = 0;
    // TODO: 对每个元素各查一次，把步数加进 total
    return to_string(best) + "/" + to_string(worst) + "/" + to_string(total / (int)a.size());
}

int main() {
    vector<bool> checks;
    checks.push_back(count_pairs(5) == 10);
    checks.push_back(grow(100) == 4);
    checks.push_back(space({17, 24, 15, 13, 23}) == "5/0");
    checks.push_back(pick(1000, 1000) == "暴力");
    checks.push_back(three_cases({13, 15, 17, 23, 24}) == "1/5/3");
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论