Python中str.replace函数的Big O表示法是什么？
str.replacePython中函数的大符号是什么？
总是O(n)吗？
str = "this is string example"
print str.replace("is", "was")
Run Code Online (Sandbox Code Playgroud)thwas was string example
Big O表示法是在最坏情况下计算的,而最坏情况下的Python源代码只是"找到substr的下一个位置,替换并进一步".一个替换执行O(n)操作(复制字符串).根据http://effbot.org/zone/stringlib.htm的一次搜索,在最坏的情况下进行O(n*m)操作.而且由于它可以达到n/m替换,总的来说应该是令人惊讶的O(n*n).
- 这种分析是错误的。首先，大O它只是数学函数的符号。当应用于算法时，我们可以指最坏、平均或最好的情况。其次，最坏情况的搜索可以是“O(k*m)”，其中“k”是查找下一个匹配项所需的字母数。因此，找到所有匹配项的最坏情况是“O(n*m)”。平均值是“O(n)”。如果你使用 Boyer-Moore，搜索就是“O(n/m)”。（遗憾的是，unicode 和 Boyer-Moore 并不是朋友。） (2认同)
我为我认为最坏的情况编写了一个测试——一个字符串一遍又一遍地重复，我们用另一个字符串替换所述字符串。因为t/n随着n增加而趋于平稳，最坏的情况在经验上似乎是这样的O(n)。但我真的无法与 @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)])
