这个循环的复杂度是多少
What's the complexity of this loop
我想弄清楚解决滑动最大值问题的这段代码的时间复杂度是多少
我尝试了 2 个嵌套循环，但复杂度为 O(n*k)，我认为下面列出的代码不那么复杂
res=[]
for i in 0..(array.length-k) do
res << array.slice(i,k).sort[-1]
end
return res
我想知道所用默认方法 (Ruby) 的复杂度是多少，以及它们如何影响此循环的复杂度。谢谢
将代码精简到最基本的部分通常会有所帮助：
(array.length-k).times.map |i|
array.slice(i,k).max
end
sort 可以在此处删除，使其成为该操作的线性时间。通常 sort 被认为是 O(log n).
这最终是O(n2)，除非你能消除内循环或外循环。
如果这里的目标是找到数组所有可能子集中的所有最大值，可能有一种算法可以做到这一点。
方法的工作原理
我可以用一个例子来解释我在这里使用的方法的基本思想。假设数组是 [1 , 3, 2, 4] 和 k = 3，我们已经计算了 [1, 3, 2].max #=> 3。那么由于1 < [1, 3, 2].max，我们知道[3, 2].max == [1, 3, 2].max #=> true。因此，我们可以通过比较两个已知值来计算[3, 2, 4].max：[[3, 2].max, 4].max => [3, 4] => 4。对于 k = 3，这是计算时间的一小部分节省，但它会随着 k 的值而增加。
计算效率
下面的方法的（最坏情况）计算复杂度为 O(n*k) (n = arr.size)，但随机生成的数组平均需要类似 (n-k)*(1+2*(k-1)/k) 的操作.
为数组的每个 k 切片 a 计算 a.max 的蛮力方法需要 (n-k)*k 操作。因此，对于随机生成的数组，我的方法所需的操作数与暴力法使用的操作数之比约为
(n-k)*(1+2*(k-1)/k)/(n-k)*k
#=> (1+2*(k-1)/k)/k
对于k = 3，这个比例是0.77，但是由于计算开销，这种方法可能仍然处于劣势。随着 k 增加，分子接近 3，因此比率接近 3/k。因此，与蛮力方法相比，随着 k 的推进，我的方法将带来越来越大的收益。
代码
def sliding_max(arr, k)
return nil if k > arr.size
(k..arr.size-1).each_with_object([arr.first(k).max]) do |i,a|
mx = a.last
a << (arr[i-k] < mx ? [mx, arr[i]] : arr[i-k+1, k]).max
end
end
例子
sliding_max([1, 4, 2, 3, 2, 1, 0], 3)
#=> [4, 4, 3, 3, 2]
sliding_max([1, 2, 3, 4, 5, 6, 7], 3)
#=> [3, 4, 5, 6, 7] (fastest)
sliding_max([7, 6, 5, 4, 3, 2, 1], 3)
#=> [7, 6, 5, 4, 3] (slowest)
说明
让我们逐步了解以下参数的方法。
arr = [1, 4, 2, 3, 2, 1, 4]
k = 3
return nil if k > arr.size
#=> return nil if 3 > 7 => false
a = [arr.first(k).max]
#=> [[1, 4, 2].max] => [4]
enum = (k..arr.size-1).each_with_object(a)
#=> #<Enumerator: 3..6:each_with_object([4])>
第一个元素生成并传递给块，块变量赋值。
i, a = enum.next
#=> [3, [4]]
i #=> 3
a #=> [4]
现在执行块计算。
mx = a.last
#=> 4
arr[i-k] < mx
#=> arr[3-3] < mx => 1 < 4 => true
所以执行
b = [mx, arr[i]].max
#=> [4, arr[3]].max => [4, 3].max => 4
a << b
#=> [4, 4]
下一个值由enum生成，传给块，块变量赋值，进行块计算。
i, a = enum.next
#=> [4, [4, 4]]
i #=> 4
a #=> [4, 4]
mx = a.last
#=> 4
arr[i-k] < mx
#=> arr[4-3] < 4 => 4 < 4 => false
所以这一次，我们必须进行更昂贵的计算。
b = arr[i-k+1, k].max
#=> arr[4-3+1, 4].max => [2, 3, 2].max => 3
a << b
#=> [4, 4, 3]
其余计算类似。
require 'benchmark'
def sliding_maximum(k, array)
time=Benchmark.realtime do
=begin
my proposition >
res=[]
for i in 0..(array.length-k) do
res << array.slice(i,k).max
end
#return res
=end # time => 8.9185999968322e-05
=begin
@Cary's proposition >
(k..array.size-1).each_with_object([array.first(k).max]) do |i,a|
mx = a.last
a << (array[i-k] < mx ? [mx, array[i]] : array[i-k+1, i]).max
end
=end # time => 0.0001353049992758315
=begin
@tadman proposition
#array.each_cons(k).map(&:max)
=end time 7.903100049588829e-05
end
p time
end
sliding_maximum(3, [1, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9])
这是我试图计算包括我在内的每个命题的实时执行的代码。随意更改传递的数组或 K 以查看执行差异。对我来说，我看到 @tadman 命题（第三个命题）对于更大的数组更快。
这是另一个基准，显示相对效率如何随着 k（每个切片的大小）增加而变化。
require 'benchmark'
def test(arr, k)
puts "Testing for k = #{k}"
Benchmark.bm(11) do |x|
x.report("Wonder Boy") {
res=[]
for i in 0..(arr.length-k) do
res << arr.slice(i,k).max
end
res
}
x.report("Tadman") { arr.each_cons(k).map(&:max) }
x.report("Cary") {
(k..arr.size-1).each_with_object([arr.first(k).max]) do |i,a|
mx = a.last
a << (arr[i-k] < mx ? [mx, arr[i]] : arr[i-k+1, k]).max
end
}
x.report("Engineer 1") {
a = arr.dup
b = a.shift(k)
max_n = n = b.max
Enumerator.new do |y|
y << max_n
loop do
break if a.empty?
b.<<(a.shift)
max_n = b.max if b.shift == max_n || b.last > max_n
y << max_n
end
end.to_a
}
x.report("Engineer 2") {
a = arr.dup
b = a.shift(k)
max_n = n = b.max
Enumerator.new do |y|
y << max_n
loop do
break if a.empty?
b.<<(a.shift)
max_n = (b.shift == max_n) ? b.max : [max_n, b.last].max
y << max_n
end
end.to_a
}
end
end
arr = 10000.times.map { rand(100) }
arr.first(4)
#=> [61, 13, 41, 82]
test(arr, 3)
Testing for k = 3
user system total real
Wonder Boy 0.021185 0.004539 0.025724 ( 0.025695)
Tadman 0.004801 0.000000 0.004801 ( 0.004809)
Cary 0.004542 0.000000 0.004542 ( 0.004568)
Engineer 1 0.003998 0.000000 0.003998 ( 0.004005)
Engineer 2 0.003427 0.000000 0.003427 ( 0.003438)
test(arr, 10)
Testing for k = 10
user system total real
Wonder Boy 0.003102 0.000000 0.003102 ( 0.003105)
Tadman 0.003205 0.000012 0.003217 ( 0.003225)
Cary 0.003286 0.000000 0.003286 ( 0.003292)
Engineer 1 0.003387 0.000000 0.003387 ( 0.003397)
Engineer 2 0.003092 0.000000 0.003092 ( 0.003100)
test(arr, 30)
Testing for k = 30
user system total real
Wonder Boy 0.011111 0.000000 0.011111 ( 0.011139)
Tadman 0.010568 0.000000 0.010568 ( 0.010572)
Cary 0.004292 0.000000 0.004292 ( 0.004301)
Engineer 1 0.004197 0.000000 0.004197 ( 0.004203)
Engineer 2 0.003759 0.000000 0.003759 ( 0.003766)
test(arr, 100)
Testing for k = 100
user system total real
Wonder Boy 0.007409 0.000035 0.007444 ( 0.007437)
Tadman 0.005771 0.000914 0.006685 ( 0.006703)
Cary 0.002773 0.000000 0.002773 ( 0.002782)
Engineer 1 0.003213 0.000000 0.003213 ( 0.003222)
Engineer 2 0.003138 0.000005 0.003143 ( 0.003150)
test(arr, 1000)
Testing for k = 1000
user system total real
Wonder Boy 0.019694 0.000000 0.019694 ( 0.019696)
Tadman 0.031178 0.012383 0.043561 ( 0.043571)
Cary 0.005782 0.000000 0.005782 ( 0.005788)
Engineer 1 0.002446 0.000000 0.002446 ( 0.002431)
Engineer 2 0.002395 0.000000 0.002395 ( 0.002396)
最具指示性的结果几乎可以肯定是 k = 100。
这是一个 Enumerator 解决方案，似乎是处理大型数据集 (k > ~65) 最快的解决方案
def sliding_max(arr,k)
a = arr.dup
b = a.shift(k)
max_n = n = b.max
Enumerator.new do |y|
y << max_n
loop do
break if a.empty?
b.<<(a.shift)
max_n = b.max if b.shift == max_n || b.last > max_n
y << max_n
end
end.to_a
end
这里我们只计算最大值，如果从数组中删除的数字等于最大值或者添加的值大于当前最大值。
我想弄清楚解决滑动最大值问题的这段代码的时间复杂度是多少
我尝试了 2 个嵌套循环，但复杂度为 O(n*k)，我认为下面列出的代码不那么复杂
res=[]
for i in 0..(array.length-k) do
res << array.slice(i,k).sort[-1]
end
return res
我想知道所用默认方法 (Ruby) 的复杂度是多少，以及它们如何影响此循环的复杂度。谢谢
将代码精简到最基本的部分通常会有所帮助：
(array.length-k).times.map |i|
array.slice(i,k).max
end
sort 可以在此处删除，使其成为该操作的线性时间。通常 sort 被认为是 O(log n).
这最终是O(n2)，除非你能消除内循环或外循环。
如果这里的目标是找到数组所有可能子集中的所有最大值，可能有一种算法可以做到这一点。
方法的工作原理
我可以用一个例子来解释我在这里使用的方法的基本思想。假设数组是 [1 , 3, 2, 4] 和 k = 3，我们已经计算了 [1, 3, 2].max #=> 3。那么由于1 < [1, 3, 2].max，我们知道[3, 2].max == [1, 3, 2].max #=> true。因此，我们可以通过比较两个已知值来计算[3, 2, 4].max：[[3, 2].max, 4].max => [3, 4] => 4。对于 k = 3，这是计算时间的一小部分节省，但它会随着 k 的值而增加。
计算效率
下面的方法的（最坏情况）计算复杂度为 O(n*k) (n = arr.size)，但随机生成的数组平均需要类似 (n-k)*(1+2*(k-1)/k) 的操作.
为数组的每个 k 切片 a 计算 a.max 的蛮力方法需要 (n-k)*k 操作。因此，对于随机生成的数组，我的方法所需的操作数与暴力法使用的操作数之比约为
(n-k)*(1+2*(k-1)/k)/(n-k)*k
#=> (1+2*(k-1)/k)/k
对于k = 3，这个比例是0.77，但是由于计算开销，这种方法可能仍然处于劣势。随着 k 增加，分子接近 3，因此比率接近 3/k。因此，与蛮力方法相比，随着 k 的推进，我的方法将带来越来越大的收益。
代码
def sliding_max(arr, k)
return nil if k > arr.size
(k..arr.size-1).each_with_object([arr.first(k).max]) do |i,a|
mx = a.last
a << (arr[i-k] < mx ? [mx, arr[i]] : arr[i-k+1, k]).max
end
end
例子
sliding_max([1, 4, 2, 3, 2, 1, 0], 3)
#=> [4, 4, 3, 3, 2]
sliding_max([1, 2, 3, 4, 5, 6, 7], 3)
#=> [3, 4, 5, 6, 7] (fastest)
sliding_max([7, 6, 5, 4, 3, 2, 1], 3)
#=> [7, 6, 5, 4, 3] (slowest)
说明
让我们逐步了解以下参数的方法。
arr = [1, 4, 2, 3, 2, 1, 4]
k = 3
return nil if k > arr.size
#=> return nil if 3 > 7 => false
a = [arr.first(k).max]
#=> [[1, 4, 2].max] => [4]
enum = (k..arr.size-1).each_with_object(a)
#=> #<Enumerator: 3..6:each_with_object([4])>
第一个元素生成并传递给块，块变量赋值。
i, a = enum.next
#=> [3, [4]]
i #=> 3
a #=> [4]
现在执行块计算。
mx = a.last
#=> 4
arr[i-k] < mx
#=> arr[3-3] < mx => 1 < 4 => true
所以执行
b = [mx, arr[i]].max
#=> [4, arr[3]].max => [4, 3].max => 4
a << b
#=> [4, 4]
下一个值由enum生成，传给块，块变量赋值，进行块计算。
i, a = enum.next
#=> [4, [4, 4]]
i #=> 4
a #=> [4, 4]
mx = a.last
#=> 4
arr[i-k] < mx
#=> arr[4-3] < 4 => 4 < 4 => false
所以这一次，我们必须进行更昂贵的计算。
b = arr[i-k+1, k].max
#=> arr[4-3+1, 4].max => [2, 3, 2].max => 3
a << b
#=> [4, 4, 3]
其余计算类似。
require 'benchmark'
def sliding_maximum(k, array)
time=Benchmark.realtime do
=begin
my proposition >
res=[]
for i in 0..(array.length-k) do
res << array.slice(i,k).max
end
#return res
=end # time => 8.9185999968322e-05
=begin
@Cary's proposition >
(k..array.size-1).each_with_object([array.first(k).max]) do |i,a|
mx = a.last
a << (array[i-k] < mx ? [mx, array[i]] : array[i-k+1, i]).max
end
=end # time => 0.0001353049992758315
=begin
@tadman proposition
#array.each_cons(k).map(&:max)
=end time 7.903100049588829e-05
end
p time
end
sliding_maximum(3, [1, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9])
这是我试图计算包括我在内的每个命题的实时执行的代码。随意更改传递的数组或 K 以查看执行差异。对我来说，我看到 @tadman 命题（第三个命题）对于更大的数组更快。
这是另一个基准，显示相对效率如何随着 k（每个切片的大小）增加而变化。
require 'benchmark'
def test(arr, k)
puts "Testing for k = #{k}"
Benchmark.bm(11) do |x|
x.report("Wonder Boy") {
res=[]
for i in 0..(arr.length-k) do
res << arr.slice(i,k).max
end
res
}
x.report("Tadman") { arr.each_cons(k).map(&:max) }
x.report("Cary") {
(k..arr.size-1).each_with_object([arr.first(k).max]) do |i,a|
mx = a.last
a << (arr[i-k] < mx ? [mx, arr[i]] : arr[i-k+1, k]).max
end
}
x.report("Engineer 1") {
a = arr.dup
b = a.shift(k)
max_n = n = b.max
Enumerator.new do |y|
y << max_n
loop do
break if a.empty?
b.<<(a.shift)
max_n = b.max if b.shift == max_n || b.last > max_n
y << max_n
end
end.to_a
}
x.report("Engineer 2") {
a = arr.dup
b = a.shift(k)
max_n = n = b.max
Enumerator.new do |y|
y << max_n
loop do
break if a.empty?
b.<<(a.shift)
max_n = (b.shift == max_n) ? b.max : [max_n, b.last].max
y << max_n
end
end.to_a
}
end
end
arr = 10000.times.map { rand(100) }
arr.first(4)
#=> [61, 13, 41, 82]
test(arr, 3)
Testing for k = 3
user system total real
Wonder Boy 0.021185 0.004539 0.025724 ( 0.025695)
Tadman 0.004801 0.000000 0.004801 ( 0.004809)
Cary 0.004542 0.000000 0.004542 ( 0.004568)
Engineer 1 0.003998 0.000000 0.003998 ( 0.004005)
Engineer 2 0.003427 0.000000 0.003427 ( 0.003438)
test(arr, 10)
Testing for k = 10
user system total real
Wonder Boy 0.003102 0.000000 0.003102 ( 0.003105)
Tadman 0.003205 0.000012 0.003217 ( 0.003225)
Cary 0.003286 0.000000 0.003286 ( 0.003292)
Engineer 1 0.003387 0.000000 0.003387 ( 0.003397)
Engineer 2 0.003092 0.000000 0.003092 ( 0.003100)
test(arr, 30)
Testing for k = 30
user system total real
Wonder Boy 0.011111 0.000000 0.011111 ( 0.011139)
Tadman 0.010568 0.000000 0.010568 ( 0.010572)
Cary 0.004292 0.000000 0.004292 ( 0.004301)
Engineer 1 0.004197 0.000000 0.004197 ( 0.004203)
Engineer 2 0.003759 0.000000 0.003759 ( 0.003766)
test(arr, 100)
Testing for k = 100
user system total real
Wonder Boy 0.007409 0.000035 0.007444 ( 0.007437)
Tadman 0.005771 0.000914 0.006685 ( 0.006703)
Cary 0.002773 0.000000 0.002773 ( 0.002782)
Engineer 1 0.003213 0.000000 0.003213 ( 0.003222)
Engineer 2 0.003138 0.000005 0.003143 ( 0.003150)
test(arr, 1000)
Testing for k = 1000
user system total real
Wonder Boy 0.019694 0.000000 0.019694 ( 0.019696)
Tadman 0.031178 0.012383 0.043561 ( 0.043571)
Cary 0.005782 0.000000 0.005782 ( 0.005788)
Engineer 1 0.002446 0.000000 0.002446 ( 0.002431)
Engineer 2 0.002395 0.000000 0.002395 ( 0.002396)
最具指示性的结果几乎可以肯定是 k = 100。
这是一个 Enumerator 解决方案，似乎是处理大型数据集 (k > ~65) 最快的解决方案
def sliding_max(arr,k)
a = arr.dup
b = a.shift(k)
max_n = n = b.max
Enumerator.new do |y|
y << max_n
loop do
break if a.empty?
b.<<(a.shift)
max_n = b.max if b.shift == max_n || b.last > max_n
y << max_n
end
end.to_a
end
这里我们只计算最大值，如果从数组中删除的数字等于最大值或者添加的值大于当前最大值。