Обращение подмассива массива менее чем за O (n) время - PullRequest
Новая
       30

Обращение подмассива массива менее чем за O (n) время

1 голос
/ 01 декабря 2011

как мы можем обратить подмассив (скажем, из i-го индекса в j-й индекс) массива (или любой другой структуры данных, такой как связанный список (не вдвойне)), менее чем за O (n) время?потребление времени O (n) тривиально (я хочу сделать это обращение много раз для массива, например, начать с начала и обратить его n раз (каждый раз, переходя к следующему индексу и затем обращая его снова),так что должен быть способ, который его амортизированный анализ даст нам время меньше, чем O (n), любая идея?
Заранее спасибо:)

Ответы [ 3 ]

4 голосов
/ 01 декабря 2011

Я думаю, что вы хотите решить это с неправильным подходом. Я предполагаю, что вы хотите улучшить алгоритм в целом, а не переворачивать O (n). Потому что это невозможно. У вас всегда есть O (n), если вам нужно рассмотреть каждый из n элементов.

Как я уже сказал, вы можете улучшить алгоритм O (n ^ 2). Вы можете решить это в O (n): Допустим, у нас есть этот список: 

a b c d e

Затем вы изменяете этот список, используя ваш алгоритм: 

e d c b a
e a b c d

и так далее ... в конце концов у вас есть это: 

e a d b c

Вы можете получить этот список, если у вас есть два указателя, приходящие с обоих концов массива и чередующиеся между указателями (значение увеличения / уменьшения / получения). Что дает вам O (n) для всей процедуры.

Более подробное объяснение этого алгоритма:

Используя предыдущий список, мы хотим, чтобы элементы были в следующем порядке: 

a b c d e
2 4 5 3 1

Итак, вы создаете два указателя. Один указывает на начало списка, другой на конец: 

a b c d e
^       ^
p1      p2

Тогда алгоритм работает следующим образом: 

1. Take the value of p2
2. Take the value of p1
3. Move the pointer p2 one index back
4. Move the pointer p1 one index further
5. If they point to the same location, take the value of p1 and stop.
   or if p1 has passed p2 then stop.
   or else go to 1.
0 голосов
/ 22 ноября 2016

Вы можете сделать это O (n) раз для данного массива. Здесь l представляет начальный индекс и r представляет конец. Таким образом, нам нужно повернуть подмассив с r на l. 

public void reverse(int[] arr, int l, int r)
  {
      int d = (r-l+1)/2;
      for(int i=0;i<d;i++)
      {
         int t = arr[l+i];
         arr[l+i] = arr[r-i];
         arr[r-i] = t;
      }
    // print array here 
  }
0 голосов
/ 01 декабря 2011

Как упоминалось в duedl0r, O (n) - ваш минимум. вам придется переместить n предметов на их новую позицию.

Поскольку вы упомянули связанный список, вот решение O (n) для этого.

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

1->2->3->4->5->6->7->8->9

изменение 4-7 изменило бы: 

4->5->6->7

в 

4<-5<-6<-7

Тогда пусть 3 указывают на 7, а 4 указывают на 8.

Несколько копирует формат duedl0r для согласованности: 

 1. Move to the item before the first item to reorder(n steps)
 2. remember it as a (1 step)
 3. Move to the next item (1 step)
 4. Remember it as b (1 step)

while not at the last item to reorder: (m times)
 5. Remember current item as c (1 step)
 6. Go to next item (1 step)
 7. Let the next item point to the previous item (1 step)

having reached the last item to reorder:
 8. let item a point to item c (1 step)

if there is a next item:
 9. move to next item (1 step)
 10. let item b point to current item (1 step)

Это O (n + 1 + 1 + 1 + m * (1 + 1 + 1) + 1 + 1 + 1). Без всех чисел, которые не допускаются в Big O, это O (n + m), которое можно назвать O (n + n), которое можно назвать O (2n).

И это O (n).

...