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

К>>Первично — понять алгоритм (хотя бы основную идею), тогда и сказать сложность не проблема.
А>Да ладно, вот есть random sort. Идея тривиальна: на каждом шаге мы сравниваем два случайных элемента и при необходимости меняем их местами. Скажи, пожалуйста, какая у него трудоемкость?
Если подойти серьёзно, то следует взглянуть на свойства того, что называется алгоритмом (собственно то, для чего считается алгоритмическая сложность). А конкретно твой random sort не обладает свойством детерминированности. По той же ссылке написано, что делать со случайными данными: "Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.". И сложность тогда считается тривиально.

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