Pythonコードの複雑さ

Question

私はこのPythonプログラムの実行時の複雑さを見出そうとしています。 index<len(lyst)-1があるため、複雑さは、まだn個になりますか、私はあなたの関数の各再帰呼び出し

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)) 

Answer 1

元のコードは壊れています。 1ステップしか必要とせず、最後の要素が所望のものであるかどうかを確認した。number。それはO（1）でしたが、関数名が行うべきことを暗示していませんでした。再帰呼び出しは決して起こらず、lystはスライスされませんでした。

更新されたコードはO（n ** 2）で実行されます。最悪の場合、平均でn/2番目のインデックスのnスライスになります。それは必要以上に遅く、再帰呼び出しのために、どのインデックスに番号が見つかったかを言うことはできません。

引数として最後のインデックスを渡して、lystをそのまま残すと、O（n）で実行される可能性があります。しかし、あなたは再帰呼び出しを必要としません。単純なループです。

ソートされたlystでは、バイナリ検索でO（log n）で実行できます。

Answer 2

時間と空間の複雑さのために新しいリストを作成していて、それがn以上になりますこと、両方O（1）です常に偽です。