🔴 有输入低于下界，这矛盾吗

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

下界算出来是 7。数一数 120 种输入里，归并排序用了不到 7 次就排完的有几种，再报出最坏的那一档。

提交你的答案

请登录后提交答案。

去登录

← 两种排序的最坏比较次数归并离理论极限还差几次 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

import math
from itertools import permutations

def merge_cmp(a):
    """归并排序，返回比较次数"""
    c = 0
    def go(x):
        nonlocal c
        if len(x) <= 1:
            return x
        m = len(x) // 2
        L, Rr = go(x[:m]), go(x[m:])
        out, i, j = [], 0, 0
        while i < len(L) and j < len(Rr):
            c += 1
            if L[i] <= Rr[j]:
                out.append(L[i]); i += 1
            else:
                out.append(Rr[j]); j += 1
        return out + L[i:] + Rr[j:]
    go(list(a))
    return c

def ins_cmp(a):
    """插入排序，返回比较次数"""
    a = list(a); c = 0
    for i in range(1, len(a)):
        j, x = i - 1, a[i]
        while j >= 0:
            c += 1
            if a[j] <= x:
                break
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = x
    return c

P = list(permutations(range(5)))
lower = math.ceil(math.log2(math.factorial(5)))

# TODO: 数一数有多少种输入，归并用的比较次数**低于**这个下界
below = -1
# TODO: 最坏的那一档是多少次
worst = -1

print(str(lower) + "/" + str(below) + "/" + str(worst))

本次输入：

输出：

👩‍🏫

💬 题目评论

🔴 有输入低于下界，这矛盾吗

更多题目

全部评论