算法的大O复杂度
算法的大O复杂度
提问于 2017-02-20 12:25:50
此方法试图将num表示为arr中元素的乘积。
例如，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 如果你能给我一些帮助来推导算法的复杂性，我会非常感激的。也请随时提高我的算法的效率
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-02-20 14:12:56
下面是你可以做的：
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表示输入数组的大小。
Stack Overflow用户
发布于 2017-02-20 17:20:46
以下是代码的重构版本：
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)。如果有必要(O(1))，附加1也可能是一个好主意。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42336499
复制相关文章
相似问题
腾讯云开发者
