알고리즘의 Big O 복잡도

Question

이 메서드는 num을 ar에있는 요소의 곱으로 표현하려고합니다. 예 방법 항목에 대한

(37, [1,3,5]) 반환 [2,0,7]

// arr is an array of divisors sorted in asc order, e.g. [1,3,5] 
def method1(num, arr) 
    newArr = Array.new(arr.size, 0) 
    count = arr.size - 1 

    while num > 0 
    div = arr[count] 

    if div <= num 
     arr[count] = num/div 
     num = num % div 
    end 

    count = count - 1 
    end 

    return newArr 
end 

당신이 나에게 알고리즘의 복잡성을 유도하기 위해 도움을 줄 수 있다면

정말 감사겠습니까 . 또한 내 알고리즘의 효율성을 향상 주시기 바랍니다

다음

Answer 1

당신이 할 수있는 작업은 다음과 같습니다

def method1(num, arr) 

    newArr = Array.new(arr.size, 0) 
    count = arr.size()-1 

    while num>0 
     div = arr[count] 

     if div <= num 
      arr[count] = num/div 
      num = num % div 
     end 

     count = count + 1 
    end 
    return arr 
end 


ar = Array.new(25000000) { rand(1...10000) } 

t1 = Time.now 
method1(37, ar) 
t2 = Time.now 

tdelta = t2 - t1 

print tdelta.to_f 

출력 :

ar = Array.new(50000000) { rand(1...10) } 

:

0.102611062 

이제 배열의 크기를 두 배로 출력 :

그리고 다시 한 번 5,752,565,325,958,786,389,123,210 :

는

ar = Array.new(100000000) { rand(1...10) } 

출력 : 그래서 n 복식

0.973402568 

은, 기간은 대략 세배. O (3n) == O (n)이므로 전체 알고리즘은 O (n) 시간에 실행됩니다. 여기서 n은 입력 배열의 크기를 나타냅니다.

Answer 2

여기에 코드의 리팩토링 버전입니다 :

def find_linear_combination(num, divisors) 
    results = divisors.map do |divisor| 
    q, num = num.divmod(divisor) 
    q 
    end 
    results if num == 0 
end 

puts find_linear_combination(37, [5, 3, 1]) == [7, 0, 2] 
puts find_linear_combination(37, [1, 3, 5]) == [37, 0, 0] 
puts find_linear_combination(37, [5]).nil? 

divisors의 크기 인 n으로,이 알고리즘은 명확 O(n) 것으로 보인다. 단 하나의 루프 (map)가 있으며 루프 내부에 단 하나의 정수가 있습니다.

약수는 내림차순으로 작성해야합니다. 선형 조합이 없으면이 메소드는 nil을 리턴합니다.

divisors을 정렬하려는 경우 알고리즘은 O(n*log n)이됩니다. 필요한 경우 1을 추가하는 것도 좋은 방법입니다 (O(1)).