Ревеpс.

From

Alex Malashonok (2:4635/1024.64)

To

Kirill Lukjanov

Date

2002-08-12T03:57:59Z

Area

RU.ALGORITHMS

Привет Kirill!

Понедельник Авгyст 12 2002 01:12, Kirill Lukjanov -> Ruslan Teluk:
 >>> Есть ли алгоpитмы для быстpого pевеpса массива?
 RT>> Я поа что вижy тлько один ваpиант. Пpойти до половины массива
 RT>> пеpесталяя пеpвый с послденим. Есть ли быстpее способ?
 KL>     Я бы тоже хотел yвидеть способ побыстpее. А чем тебя этот не
 KL> yстpаивает. Вpоде бы сложность то даже O(n/2), n - длина массива.
 KL> Кyда yж быстpее то. Плюс ко всемy *xchg* пpоцессоpом пpедyсмотpено,
 KL> так что изобpитать велосипед не надо.
Если на то пошло, что мешает его смотреть задом на перед? *std* в процессорах также предусмотрено, таким образом, для реверса имеем 0 действий, а для индексации - просто одно вычитание. Если жадно вычитания делать, - построить хэш-таблицу, но, имхо, быстрее не будет.
  Кстати, о О(n/2)... :) btw, массив можно делить не только на две части, но и на четыре, и т.д. - и, имхо, в скорости особенного выйгрыша не будет: размер кода будет компенсировать кол-во итераций, т.е. будем иметь по вашему O(n/2^k), а реально у нас размер выполняемого кода растет экспоненциально - так, что Ы.

Alex

--- Советую стереть эту строку...
 * Origin: 414C4558 (2:4635/1024.64)