Che cos'è la notazione Big O per la funzione str.replace in Python?

Question

Qual è la funzione di grande notazione Oh per la funzione str.replace in Python?

È sempre O (n)?

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

thwas was string example 

Answer 1

notazione O-grande è calcolato scenario nel peggiore dei casi, e le fonti di Python per caso peggiore si limitano a 'trovare successiva posizione di substr, sostituire, e andare oltre'. Una sostituzione esegue operazioni O (n) (copia della stringa). Una ricerca, secondo lo http://effbot.org/zone/stringlib.htm, nella peggiore delle ipotesi fa operazioni di O (n * m). E dal momento che può essere fino a n/m sostituzioni, in totale dovrebbe essere sorprendentemente O (n * n).

Answer 2

Ho codificato un test per quello che ritengo sia lo scenario peggiore, una stringa ripetuta più e più volte e stiamo sostituendo la stringa con un'altra stringa. Poiché i livelli t/n disattivano come aumenti n, lo scenario peggiore sembra empiricamente come potrebbe essere O(n). Ma non posso davvero discutere con il post di @NickolayOlshevsky.

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