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

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

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

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

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