Big O Сложность алгоритма

Question

Этот метод пытается выразить num как произведение элементов в обр.

Для например method1 (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 

Выход:

0.102611062 

Теперь двойной размер массива:

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

Выход:

0.325793964 

И снова дважды:

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

Выход:

0.973402568 

так что n двойники, длительность примерно в три раза. Поскольку 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? 

С n быть размером divisors, этот алгоритм ясно, как представляется, O(n). Есть только один цикл (map), и внутри цикла есть только одно целочисленное деление.

Обратите внимание, что делители должны быть записаны в порядке убывания. Если линейная комбинация не найдена, метод возвращает nil.

Если вы хотите отсортировать divisors, алгоритм будет O(n*log n). Также неплохо было бы добавить 1 (O(1)).