gsub的时间复杂度

Question

长字符串s仅包含0和1。这Ruby代码计数多少1有：

s.gsub(/1/).count 

什么是大O符号的时间复杂度？有没有一个工具来做计算？

Answer 1

据我所知，没有一种通用的工具来计算任意代码的大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) 

您可以采取从基准的返回值，并用它们来自动在大O.这是一个猜测可能是像编纂一样的服务。