gsub的时间复杂度 [英] Time complexity of gsub

问题描述

长字符串s仅包含0和1.这段Ruby代码会统计有多少1:

A long string s contains only 0 and 1. This Ruby code counts how many 1 there are:

s.gsub(/1/).count

Big O表示法的时间复杂度是多少?有计算工具吗?

What is the time complexity in Big O notation? Is there a tool to do the calculation?

推荐答案

据我所知，没有通用的工具可以为任意代码计算Big O符号-这将是一项艰巨的任务-首先，它不是始终清除要衡量的缩放问题.即使是非常简单的逻辑，a = b + c也不会像您想象的那样扩展-如果您需要允许任意大的数字，则不是 O( 1 ).

As far as I know there is not a generic tool to calculate Big O notation for arbitrary code - this would be a hard task - for a start it is not always clear which scaling issue to measure. Even very simple logic, a = b + c does not scale as you might think - if you need to allow for arbitrarily large numbers then this is not O( 1 ).

最简单的方法是进行基准测试并绘制结果.您应该意识到，对于高效代码，可以通过例如方法调用开销来淹没"缩放度量.因此，需要花费一些精力-您需要找到足够大的N值，使其倍增会产生很大的不同.

The simplest thing to do is benchmark and plot the results. You should be aware that for highly efficient code that the scaling measure can be "drowned out" by for example method-calling overhead. So it takes a little effort - you need to find values of N large enough that doubling it makes a significant difference.

要验证您的命令的字符串长度为O( N )，我运行了以下基准测试:

To verify that your command is O( N ) on string length, I ran the following benchmarks:

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)

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

By inspection you can see this is a simple linear relationship - every time I double the length of the string, the time taken (roughly) doubles.

顺便说一句，s.count('1')快很多，而且也O( N ):

By the way, s.count('1') is much, much faster, but is also 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之类的服务所要做的.

You could take the return values from benchmarking, and use them to automate a guess at Big O. This is probably what services like codility do.

这篇关于gsub的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！