gsub的时间复杂度

一根长绳子s仅包含0 and 1。这段 Ruby 代码计算了有多少个1有：

s.gsub(/1/).count

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

据我所知，没有一个通用工具可以计算任意代码的 Big O 表示法 - 这将是一项艰巨的任务 - 首先，并不总是清楚要衡量哪个缩放问题。即使是非常简单的逻辑，a = b + c不会像您想象的那样缩放 - 如果您需要允许任意大的数字，那么这就是not 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)

You could从基准测试中获取返回值，并使用它们自动猜测 Big O。这可能就是像 codility 这样的服务所做的事情。