python代码的复杂性

我正在尝试查找此Python程序的运行时复杂性。将复杂度静像N还是会超过n，因为我每个递归调用python代码的复杂性

def RecLinearSearch(lyst,number): 
    found = False 
    index = len(lyst)-1 
    if lyst[index] == number: 
     found = True 
     return found 
    elif index<len(lyst)-1: 
     index +=1 
     return RecLinearSearch(lyst[index:],number) 
    return found 
print(RecLinearSearch([1,4,5,65,44],55))

来源

2017-04-01 Ritika Manwani

请使用代码块。 –

您是在谈论内存或运行时复杂性？ – UnholySheep

运行时复杂性 –

您的原始代码已损坏。它只需要1步，并检查最后一个元素是否是所需的number。这是O（1），但没有做功能名称暗示它应该做的事情。递归调用从未发生，并且lyst从未切片。

您更新后的代码在O（n ** 2）中运行：最差的情况是平均值为n/2th指数。它比必要的慢，并且由于递归调用，不可能说出在哪个索引处找到了该号码。

如果您将最后一个索引作为参数传递并且会保持lyst不变，它可以在O（n）中运行。但是，你也不需要递归调用，只需一个简单的循环。

使用排序后的lyst，它可以用二进制搜索在O（log n）中运行。

来源

2017-04-01 11:29:12

我编辑了问题 –

@RitikaManwani：我编辑了答案;） –

感谢编辑这回答我的问题:) –

时间和空间复杂的功能创建一个新的列表都O（1），因为index<len(lyst)-1是总是假的。

来源

2017-04-01 11:12:28

python代码的复杂性

回答

相关问题