ruby - 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 这样的服务所做的。