Сложность времени gsub

Question

Длина длинной строки s содержит только и 1. Этот подсчет кода Руби, сколько 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. This вероятно, то, что делают такие сервисы, как кодовость.