Wie lautet die Big-O-Notation für die Funktion str.replace in Python?

Question

Was ist die große Oh-Notation für str.replace Funktion in Python?

Ist es immer O (n)?

str = "this is string example" 
print str.replace("is", "was") 

thwas was string example 

Answer 1

Big O-Notation ist im Worst-Case-Szenario berechnet, und Python Quellen für den ungünstigsten Fall kann nur 'nächste Position von substr, ersetzen und gehen weiter finden'. Eine Ersetzung führt O (n) -Operationen durch (Kopieren der Zeichenfolge). Eine Suche, nach http://effbot.org/zone/stringlib.htm, im Worst-Case-Szenario funktioniert O (n * m). Und da es bis zu n/m Ersatz sein kann, sollte insgesamt O (n * n) überraschend sein.

Answer 2

Ich habe einen Test für das, was ich glaube, ist der Worst-Case-Szenario - eine Zeichenfolge wiederholt und wiederholt, und wir ersetzen diese Zeichenfolge durch eine andere Zeichenfolge. Da sich t/n als n erhöht, scheint Worst-Case-Szenario empirisch wie es O(n) sein kann. Aber ich kann wirklich nicht mit @NickolayOlschevsky's Beitrag argumentieren.

import time 
from matplotlib import pyplot as plt 

x=[10] 
while x[-1]<10**8: 
    x.append(int(x[len(x)-1]*1.5)) 

y = [0]*len(x) 

nst = 'abcd' 
sst = 'abcd' 

for ix,i in enumerate(x): 
    s = ''.join([nst]*i) 
    t = time.time() 
    s = s.replace(sst,'efgh') 
    y[ix] = time.time()-t 

x = [a*len(nst) for a in x] 

%matplotlib inline 
fig, (ax1,ax2) = plt.subplots(2, sharex=True) 
fig.set_size_inches(8, 6) 
ax1.set_xscale('log') 
ax1.set_yscale('log') 
ax1.set_xlabel('n') 
ax1.set_ylabel('t') 
ax1.plot(x,y) 
ax2.set_xscale('log') 
ax2.set_yscale('log') 
ax2.set_xlabel('n') 
ax2.set_ylabel('t/n') 
ax2.plot(x,[a/b for a,b in zip(x,y)])