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


DR>Проверка отсортированнасти массива — O(n); вероятность того, что массив отсортирован — 1/n!. Средняя сложность — O(n*n!).
Да ладно, через O(n^4) должен останавливаться в среднем.