算法的大O复杂度
Big O Complexity of Algorithm
此方法试图将 num 表示为 arr 中元素的乘积。
例如方法 1(37,[1,3,5]) returns [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
如果您能帮我推导算法的复杂度,我将不胜感激。也请随时提高我的算法效率
您可以执行以下操作:
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 表示输入的大小
数组。
这是您的代码的重构版本:
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
)并且循环内只有一个整数除法
注意除数要按降序排列。如果没有找到线性组合,方法returns nil.
如果要排序 divisors
,算法将是 O(n*log n)
。如有必要,附加 1
也是一个好主意 (O(1)
)。
此方法试图将 num 表示为 arr 中元素的乘积。
例如方法 1(37,[1,3,5]) returns [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
如果您能帮我推导算法的复杂度,我将不胜感激。也请随时提高我的算法效率
您可以执行以下操作:
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 表示输入的大小
数组。
这是您的代码的重构版本:
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
)并且循环内只有一个整数除法
注意除数要按降序排列。如果没有找到线性组合,方法returns nil.
如果要排序 divisors
,算法将是 O(n*log n)
。如有必要,附加 1
也是一个好主意 (O(1)
)。