平均时间复杂度

我有一个递归函数，你可以从下面看到。我也有相同功能的迭代版本。我的问题是关于递归函数的时间复杂度。根据我的知识，它应该是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

来源

2014-01-29 Güngör Basa

请显示您的迭代版本。 – rendon

@rendon我加了迭代函数 –

你看过'count + = sum（arr [i]> arr [i：]）'是否提高了速度，假设'arr'是一个NumPy数组，并且对函数理解外面的'我'而不是把它放在一个循环中？ – ssm

我不完全理解的递归版本，但我认为这个问题是此行：

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

每当你打电话给t他正在创建你的列表副本的递归函数，这个操作很耗时。根据列表的大小，这可能会严重影响算法的性能。真的有必要创建一个副本吗？

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

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]) ...。

来源

2014-01-29 03:47:14 rendon

其实没有。我只需要计算倒数。这是关于时差的原因吗？ –

这是一个可能的原因。你的名单的大小是多少？ OMG。 – rendon

大小的列表是10.000 –

平均时间复杂度

回答

相关问题