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.這是一個猜測可能是像編纂一樣的服務。