Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Константин, Вы писали:

К>>Первично — понять алгоритм (хотя бы основную идею), тогда и сказать сложность не проблема.

А>Да ладно, вот есть random sort. Идея тривиальна: на каждом шаге мы сравниваем два случайных элемента и при необходимости меняем их местами. Скажи, пожалуйста, какая у него трудоемкость?

А>А ведь это тривиальный алгоритм, а если взять что-нибудь типа обхода дерева по алгоритму пьяной макаки или поиск пути по B* c эвристиками.

Я что-то упускаю или это правда тривиально? Разумеется задачу надо "додумать", условие то неполно. Пусть элементарная операция — генерация двух индексов, сравнение и обмен. А условие остановки — массив отсортирован. Вероятность совершить последний обмен в массиве длины k: 1/k * 1/k = 1 / (k^2). Т.е. в среднем понадобится O(k^2) операций. Затем рассмотрим отсортированный массив длины N как последовательность отсортированных массивов длины k.
Проинтегрируем по k от 0 до N. Получим O(N^3). Какие тут трудности могут быть с этим алгоритмом?