ruby – gsub的时间复杂度

s.gsub(/1/).count

据我所知,没有一个通用的工具来计算任意代码的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这样的服务.