В чем сложность этого цикла

Question

Я пытаюсь выяснить, какова временная сложность этого кода, который решает проблему скользящего максимума

Я пробовал с 2-мя вложенными циклами, но это было бы со сложностью O (n * k), и ядумаю, что приведенный ниже код менее сложен

  res=[]
  for i in 0..(array.length-k) do 
   res <<  array.slice(i,k).sort[-1]
  end
  return res 

Я хочу знать, какова сложность используемых по умолчанию методов (Ruby) и как они влияют на сложность этого цикла.Спасибо

Answer 1

Здесь решение 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 или добавляемое значение больше текущего максимума.

Answer 2

Вот еще один тест, который показывает, как изменяется относительная эффективность при увеличении 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.

Answer 3

Как работает метод

Я могу объяснить основную идею подхода, который я использовал здесь, на примере.Предположим, что массив был [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 для каждого 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]

Остальные расчеты аналогичны.

Answer 4

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 (третье) быстрее для больших массивов.

Answer 5

Часто помогает начать, сводя код к основам:

(array.length-k).times.map |i|
  array.slice(i,k).max
end

Где sort может быть удалено здесь, делая линейное время для этой операции. Обычно sort считается O (log n) .

Это в конечном итоге O (n ² ) , если вы не можете устранить внутренний или внешний цикл.

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