gsub的时间复杂度

Question

一个长字符串s只包含0和1.这个Ruby代码计算有多少1:

s.gsub(/1/).count

Big O表示法的时间复杂度是多少？有没有工具可以进行计算？

Answer 1

据我所知,没有一个通用工具来计算任意代码的Big O表示法 - 这将是一项艰巨的任务 - 首先,并不总是清楚要测量哪个缩放问题.即使是非常简单的逻辑,a = b + c也不会像你想象的那样扩展 - 如果你需要允许任意大数,那么这不是 O( 1 ).

最简单的方法是对结果进行基准测试和绘图.您应该知道,对于高效的代码,缩放度量可以通过例如方法调用开销"淹没".因此需要花费一点力气 - 你需要找到足够大的N值,使其倍增会产生显着的差异.

为了验证您的命令是否O( N )在字符串长度上,我运行了以下基准测试:

require 'benchmark'

def times_for length
  str = '012123132132121321313232132313232132' * length
  Benchmark.bm do |x|
    x.report( :gsub ) { 1000.times { str.gsub(/1/).count } }
  end
end

times_for 250
       user     system      total        real
gsub  1.510000   0.000000   1.510000 (  1.519658)


times_for 500
       user     system      total        real
gsub  2.960000   0.000000   2.960000 (  2.962822)


times_for 1000
       user     system      total        real
gsub  5.880000   0.010000   5.890000 (  5.879543)

通过检查,您可以看到这是一个简单的线性关系 - 每次我将字符串的长度加倍时,所用的时间(大致)就会翻倍.

顺便说一下,s.count('1')更快,更快,但也是O( N ):

times_for 250
       user     system      total        real
count  0.010000   0.000000   0.010000 (  0.008791)

times_for 500
       user     system      total        real
count  0.010000   0.000000   0.010000 (  0.016489)

times_for 1000
       user     system      total        real
count  0.020000   0.000000   0.020000 (  0.029052)

您可以从基准测试中获取返回值,并使用它们自动猜测Big O.这可能是像codility这样的服务.