我已经在 python 中编写了这个中位数算法的实现,但它似乎没有输出正确的结果,而且对我来说它似乎也不是线性复杂性,知道我在哪里偏离轨道吗?

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
    Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

该函数的调用方式如下:
L = list(range(100))
shuffle(L)
print(select(L))

乐:对不起。 GetMed 是一个函数,它只是对列表进行排序并返回 len(list) 处的元素,它应该在那里选择,我现在修复了它,但仍然得到错误的输出。至于缩进,代码运行没有错误,我认为它没有任何问题:-??

LE2:我期待 50(对于当前的 L),它给了我 30 到 70 的输出,不多不少(还)

LE3:非常感谢,这已经成功了。我很困惑,我试图在这种方法和简单的方法之间进行比较,在那里我只是对数组进行排序并输出结果。现在,从我目前读到的内容来看, select 方法的时间复杂度应该是 O(n) Deterministic Selection 。虽然我可能无法与 python 开发人员所做的优化竞争,但我确实期望得到比我得到的更接近的结果,例如,如果我将列表的范围更改为 10000000,则选择在 84.10837116255952 秒内输出结果,而排序和返回方法在 18.92556029528825 中进行。有什么好方法可以使这个算法更快?

最佳答案

1)你的代码缩进是错误的,试试这个:

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
        Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

2)您使用的方法不返回中位数,它只返回一个离中位数不远的数字。要获得中位数,您需要计算有多少数字大于您的伪中位数,如果多数更大,则用大于伪中位数的数字重复算法,否则用其他数字重复。
def select(L, j):
    if len(L) < 10:
        L.sort()
        return L[j]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        Meds.append(select(subList, int((len(subList)-1)/2)))
    med = select(Meds, int((len(Meds)-1)/2))
    L1 = []
    L2 = []
    L3 = []
    for i in L:
        if i < med:
            L1.append(i)
        elif i > med:
            L3.append(i)
        else:
            L2.append(i)
    if j < len(L1):
        return select(L1, j)
    elif j < len(L2) + len(L1):
        return L2[0]
    else:
        return select(L3, j-len(L1)-len(L2))

警告:L = M = [] 不是 L = []M = []

关于 "median of medians"算法的 Python 实现,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10806303/

10-16 10:23