Komplexität des Python-Codes

Question

Ich versuche, die Laufzeit Komplexität dieses Python-Programms zu finden. noch n oder wird es mehr als n wird die Komplexität sein, wie ich für jeden rekursiven Aufruf

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

Ihr ursprünglicher Code wurde beschädigt. Es wurde nur 1 Schritt benötigt und überprüft, ob das letzte Element das gewünschte number ist. Es war O (1), hat aber nicht getan, was der Funktionsname impliziert. Der rekursive Aufruf ist nie erfolgt und die lyst wurde nie geschnitten.

Ihr aktualisierter Code läuft in O (n ** 2): Der schlechteste Fall wäre n Slices im Durchschnitt n/2 Index. Es ist langsamer als nötig und aufgrund der rekursiven Aufrufe ist es nicht möglich zu sagen, bei welchem ​​Index die Nummer gefunden wurde.

Wenn Sie den letzten Index als Argument übergeben und die lyst unverändert lassen, könnte sie in O (n) ausgeführt werden. Aber Sie brauchen auch keinen rekursiven Aufruf, nur eine einfache Schleife.

Mit einer sortierten lyst könnte es in O (log n) mit einer binären Suche laufen.

Answer 2

Zeit und Raum Komplexität Ihrer Funktion eine neue Liste erschaffe sind beide O (1), da index<len(lyst)-1 ist immer falsch.