小编vic*_*hle的帖子

我上周在学校做了一项任务,实现了计算斐波纳契数列中第n个数的函数."子指派"是使用累积(可能不是正确的翻译)来实现它,以便给出函数O(n)时间复杂度.这一切都很好,直到我尝试制作函数(Int - > Integer).通过实验,我意识到时间复杂度对于非常大的数字接近于O(n ^ 2).在我看来,这必须是因为Integer的实现,这使我对它的工作方式有点好奇.我做了一些谷歌搜索,没有找到任何看似有用的东西,所以我转向你们,希望得到一个解释或一个解释彻底的链接.

我的代码:

ackfib 0 = 0
ackfib 1 = 1        
ackfib n = loop n 1 0 1
    where
        loop n n1 n2 i 
            | i < n     = loop n (n1+n2) n1 (i+1)
            | i == n    = n1
            | i > n     = error "n must be greater than or equal to 0"

我很感谢所有答案

尤

我从这个mergesort实现得到意外(？)结果.与我的三向快速排序(也用python编写)相比,它非常慢.

我的quicksort在大约0.005s后完成10000个元素,而mergesort需要1.6s!包括两个实现的源代码.

归并:

#Merges two sorted lists into one sorted list. recursively
def merge(left, right):
    if len(left) == 0 and len(right) == 0:
        return []
    elif len(left) == 0:
        return right
    elif len(right) == 0:
        return left
    else:
        if left[0] <= right[0]:
            return left[:1] + merge(left[1:],right)
        else:
            return right[:1] + merge(left,right[1:])

#Splits a list in half and returns the halves
def halve(list):
    return list[:len(list)//2],list[len(list)//2:]

#Mergesort
def mergesort(list):
    if len(list) <= 1:
        return list
    left,right = halve(list)
    left,right = mergesort(left),mergesort(right)
    return …