Есть у меня алгоритм над массивом. Он производит смещение массива, т.е. в массиве 10 элементов, он может взять n первых элементов — задвинуть их в конец, а те что там были поместить в начало. Это О(N) в худшем случае и O(1) в лучшем?

Здравствуйте, Gattaka, Вы писали:

G>Есть у меня алгоритм над массивом. Он производит смещение массива, т.е. в массиве 10 элементов, он может взять n первых элементов — задвинуть их в конец, а те что там были поместить в начало. Это О(N) в худшем случае и O(1) в лучшем?

Для классического алгоритма циклический сдвиг для массива выполняется за O(N), где N — длина массива, и не зависит от величины сдвига. O(1) может быть только для нулевого сдвига, что в качестве лучшего случая учитывать как-то неприлично.

Здравствуйте, MBo, Вы писали:

MBo>Здравствуйте, Gattaka, Вы писали:

G>>Есть у меня алгоритм над массивом. Он производит смещение массива, т.е. в массиве 10 элементов, он может взять n первых элементов — задвинуть их в конец, а те что там были поместить в начало. Это О(N) в худшем случае и O(1) в лучшем?

MBo>Для классического алгоритма циклический сдвиг для массива выполняется за O(N), где N — длина массива, и не зависит от величины сдвига. O(1) может быть только для нулевого сдвига, что в качестве лучшего случая учитывать как-то неприлично.

А где он пишет про циклический? Он пишет про обмен головы и хвоста — это всегда O(1). Точнее, это точно не зависит от длины массива, но зависит от числа меняемых элементов. Так что O(M), где M — число перемещаемых элементов.

Здравствуйте, bzig, Вы писали:



B>А где он пишет про циклический?

Ну сам же процитировал вопрос:

G>>>Есть у меня алгоритм над массивом. Он производит смещение массива, т.е. в массиве 10 элементов, он может взять n первых элементов — задвинуть их в конец, а те что там были поместить в начало. Это О(N) в худшем случае и O(1) в лучшем?

Это и называется циклическим сдвигом

{0,1,2,3,4,5,6}=>{5,6,0,1,2,3,4}

Здравствуйте, Gattaka, Вы писали:

G>Есть у меня алгоритм над массивом. Он производит смещение массива, т.е. в массиве 10 элементов, он может взять n первых элементов — задвинуть их в конец, а те что там были поместить в начало. Это О(N) в худшем случае и O(1) в лучшем?

В чем собствено вопрос?. Где алгоритм?

data[ (pos+ofs) % size ]

> Это и называется циклическим сдвигом

Ну я даже не знаю. Тебе уже указали, что ты не прав, а ты вместо того, чтобы перечитать вопрос опять пишешь чепуху.