我试图找出解决滑动最大问题的代码的时间复杂度
我尝试了2个嵌套循环，但这将是复杂的O（n * k），我认为下面列出的代码不那么复杂
res=[]
for i in 0..(array.length-k) do
res << array.slice(i,k).sort[-1]
end
return res
我想知道使用的默认方法（Ruby）的复杂性以及它们如何影响这个循环的复杂性。谢谢
这是另一个基准，它显示了相对效率如何随着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
这里我们只计算max，如果从数组中删除的数字等于max或者添加的值大于当前最大值。
将代码简化为基本要素通常会有所帮助：
(array.length-k).times.map |i|
array.slice(i,k).max
end
可以在这里剥离sort，使其成为该操作的线性时间。通常sort被认为是O（log n）。
除非你能消除内环或外环，否则这最终是O（n2）。
如果这里的目标是找到数组的所有可能子集中的所有最大值，那么可能有一种算法可以做到这一点。
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命题（第三个）对于更大的数组更快。
该方法如何工作
我可以通过一个例子来解释我在这里使用的方法的基本思想。假设数组是[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)操作。
为阵列的每个a.max-slice k计算a的蛮力方法需要(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]
剩下的计算是类似的。