归并离理论极限差几次

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

把下界、归并的最坏比较次数、以及两者的差一起输出。

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

提交你的答案

请登录后提交答案。

去登录

← 有输入低于下界矛盾吗摊还和平均情况差在哪 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

vector<int> merge_go(const vector<int>& x, int& c) {
    if (x.size() <= 1) return x;
    size_t m = x.size() / 2;
    vector<int> L = merge_go(vector<int>(x.begin(), x.begin() + m), c);
    vector<int> R = merge_go(vector<int>(x.begin() + m, x.end()), c);
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < L.size() && j < R.size()) {
        c++;
        if (L[i] <= R[j]) out.push_back(L[i++]);
        else out.push_back(R[j++]);
    }
    out.insert(out.end(), L.begin() + i, L.end());
    out.insert(out.end(), R.begin() + j, R.end());
    return out;
}

int merge_cmp(const vector<int>& a) {   // 归并排序，返回比较次数
    int c = 0;
    merge_go(a, c);
    return c;
}

int ins_cmp(vector<int> a) {            // 插入排序，返回比较次数
    int c = 0;
    for (size_t i = 1; i < a.size(); i++) {
        int x = a[i];
        int j = (int)i - 1;
        while (j >= 0) {
            c++;
            if (a[j] <= x) break;
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
    return c;
}

vector<vector<int>> all_perms() {
    vector<int> p = {0, 1, 2, 3, 4};
    vector<vector<int>> out;
    do { out.push_back(p); } while (next_permutation(p.begin(), p.end()));
    return out;
}

int main() {
    // TODO: 三个数——下界、归并最坏、归并最坏比下界多几次
    int a = -1, b = -1, c = -1;
    cout << a << "/" << b << "/" << c << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

归并离理论极限差几次

更多题目

全部评论