Quote
Определение2 :
Введём функцию, которая по графу сравнений G , будет возвращать число способов сопоставить элементы массива из n числе , таким образом , чтобы это не противоречило графу G и назовем её T.Очевидно что результатом каждого алгоритма сортировки должен быть линейный граф , а у линейного графа T(G)=1
Проще сказать, что это кол-во перестановок, удовлетворяющих графу Руслан, у тебя ошибооок! 
Добавлено (15.05.2010, 23:05)
---------------------------------------------
Quote
E*= E(G* , k^)=n!/(ceiling(log2 n!))
Там степень двойки, а не просто ceiling(log2 n!)Добавлено (15.05.2010, 23:07)
---------------------------------------------
Ты забыл сказать, что эффективность после каждого сравнения не возрастает. А по поводу меньшей эффективности - мы же строим контрпример и слепо верим, что в графе с меньшей эффективностью найдется лажа
, Заяц , Дмитрий Григорьевич 
