Самый быстрый алгоритм для кругового сдвига N измеренный массив для положения M

В зависимости от структуры данных, которую вы используете, вы можете сделать это за O (1). Я думаю, что самый быстрый способ - сохранить массив в виде связанного списка и иметь хеш-таблицу, которая может преобразовывать «индекс» в массиве в «указатель» на запись. Таким образом, вы можете найти соответствующие головы и хвосты в O (1) и выполнить переподключение в O (1) (и обновить хеш-таблицу после переключения в O (1)). Это, конечно, было бы очень "беспорядочным" решением, но если все, что вас интересует, это скорость сдвига, это подойдет (за счет более длительной вставки и поиска в массиве, но он все равно останется O ( 1))

Если у вас есть данные в чистом массиве, я не думаю, что вы можете избежать O (n).

С точки зрения программирования, это зависит от того, какой язык вы используете.

Например, в Python вы можете «разрезать»

Настройте его с помощью указателей, и это почти не займет времени. Каждый элемент указывает на следующий, а «последний» (последнего нет; в конце концов, вы сказали, что он был круговым) указывает на первый. Один указатель на «начало» (первый элемент) и, возможно, длину, и у вас есть свой массив. Теперь, чтобы сделать смену, просто проведите указателем начала по кругу.

Попросите хороший алгоритм, и вы получите разумные идеи. Попросите самый быстрый , и вы получите странные идеи!

Это просто вопрос представления. Сохраните текущий индекс как целочисленную переменную, а при обходе массива используйте оператор по модулю, чтобы знать, когда следует оборачиваться. Сдвиг тогда только изменяет значение текущего индекса, оборачивая его вокруг размера массива. Это, конечно, O (1).

Например:

int index = 0;
Array a = new Array[SIZE];

get_next_element() {
    index = (index + 1) % SIZE; 
    return a[index];
}

shift(int how_many) {
    index = (index+how_many) % SIZE;
}

Сохранение двух индексов в массиве, один индекс начинается с начала до конца массива. Другой индекс начинается с позиции M от last и проходит по последним M элементам любое количество раз. Принимает O (n) все время. Дополнительного места не требуется.

circleArray(Elements,M){
 int size=size-of(Elements);

 //first index
 int i1=0;

 assert(size>M)

 //second index starting from mth position from the last
 int i2=size-M;

 //until first index reaches the end
 while(i1<size-1){

  //swap the elements of the array pointed by both indexes
  swap(i1,i2,Elements);

  //increment first pointer by 1
  i1++;

  //increment second pointer. if it goes out of array, come back to
  //mth position from the last
  if(++i2==size) i2=size-M;

 }
}

circleArray есть некоторые ошибки, и он не работает во всех случаях!

Цикл должен продолжаться , пока i1 НЕ i1 .

void Shift(int* _array, int _size, int _moves)
{
    _moves = _size - _moves;
    int i2 = _moves;
         int i1 = -1;
         while(++i1 < i2)
    {
        int tmp = _array[i2];
        _array[i2] = _array[i1];
        _array[i1] = tmp;
        if(++i2 == _size) i2 = _moves;
    }
}