平均时间复杂度

贡戈尔·巴萨（Gungor Basa）

您可以从下面看到，我有一个递归函数。我也有相同功能的迭代版本。我的问题是关于递归函数的时间复杂度。根据我的知识，它应该是O（n ^ 2）。此功能的时间复杂度是多少？如果是O（n ^ 2）; 我用相同的输入测试两个函数（迭代递归），为什么运行时间之间有巨大差异？谢谢

迭代时差：4.045395递归时差：20.554156

def naive_dac(arr):
    if len(arr) == 1:
        return 0

    count = naive_dac(list(arr[0:len(arr) - 1]))
    for i in range(0,len(arr)):
        if int(arr[i]) > int(arr[len(arr) - 1]):
            count += 1
    return count

迭代版

def brute_force(arr):
    count = 0
    for i in range(0,len(arr)):
        for j in range(i,len(arr)):
            if arr[j] < arr[i]:
                count += 1
    return count

伦登

我不完全了解递归版本，但我认为问题是此行：

count = naive_dac(list(arr[0:len(arr) - 1]))

每次调用递归函数时，您都在创建列表的副本，此操作非常耗时。根据列表的大小，这可能会严重影响算法的性能。真的有必要创建副本吗？

假设您的算法正确并且不修改列表，则可以使用变量来存储列表的长度。

def naive_dac(arr, length):
    if length == 1:
        return 0

    count = naive_dac(arr, length - 1)
    for i in range(0, length):
        if arr[i] > arr[length-1]:
            count += 1
    return count

编辑：额外的开销是由强制转换引起的：int(arr[i]) ...。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。