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

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

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

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