gsub의 시간 복잡도

Question

긴 문자열 s에는 0 및 1 만 포함됩니다. 이 루비 코드의 수는 얼마나 많은 1이 있습니다 :

s.gsub(/1/).count 

큰 O 표기법의 시간 복잡도는 무엇입니까? 계산을 할 수있는 도구가 있습니까?

Answer 1

내가 아는 한 임의의 코드에 대해 Big O 표기법을 계산하는 일반적인 도구가 없습니다. 시작하기 전에 측정 할 스케일링 문제가 항상 명확하지는 않습니다. 생각할 수있는 것처럼 매우 단순한 논리 인 a = b + c은 비례하지 않습니다. 임의로 큰 숫자를 허용해야한다면 이 아니며O(1)이 아닙니다.

가장 간단한 방법은 벤치 마크하고 결과를 표시하는 것입니다. 매우 효율적인 코드의 경우 메서드 호출 오버 헤드와 같은 스케일링 값을 "익사시킬"수 있습니다. 따라서 약간의 노력이 필요합니다. 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) 

는이 간단한 선형 관계입니다 볼 수 있습니다

이 명령은 문자열 길이에 O(N) 있는지 확인하기 위해, 나는 다음과 같은 벤치 마크를 실행 소요 시간 (대략)은 두 배가됩니다. 그런데

, 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.이의 추측을 자동화하는 데 사용할 수 있습니다 아마도 codility와 같은 서비스가 무엇일까요?