Pour trouver la position d'une sous-chaîne, à l'intérieur d'une chaîne, un algorithme naïf prendra O(n^2)
fois. Cependant, en utilisant des algorithmes efficaces (par exemple KMP algorithm), cela peut être réalisé en O (n):python str.index temps complexité
s = 'saurabh'
w = 'au'
def get_table():
i = 0; j = 2
t = []
t.append(-1); t.append(0)
while i < len(w):
if w[i] == w[j-1]:
t.append(j+1)
j += 1
else:
t.append(0)
j = 0
i += 1
return t
def get_word():
t = get_table()
i = j = 0
while i+j < len(s):
if w[j] == s[i+j]:
if j == len(w) - 1:
return i
j += 1
else:
if t[j] > -1:
i = i + j - t[j]
j = t[j]
else:
i += 1
return -1
if __name__ == '__main__':
print get_word()
Cependant, si nous le faisons: 'saurabh'.index('ra')
, il n'utilise en interne un algorithme efficace pour calculer cela en O(n)
ou il utilise un algorithme de complexité naïf O(n^2)
?
Vous pouvez le profil et voir si le temps croît de façon exponentielle ou linéaire; –