КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Понятие сложности в среднемДо сих пор мы исследовали сложность в худшем случае, теперь обратимся к сложности в среднем. Мы ограничимся ситуацией, когда при каждом фиксированном значении s размера входа сами соответствующие входы образуют конечное множество Xs = {x: || x ||= s }. Будем предполагать, что каждому xeXs приписана некоторая вероятность P s (x): О ^ P s (x) О, и при этом Таким образом, при каждом допустимом значении s размера входа множество Xs превращается в вероятностное пространство; по умолчанию считается, что вероятность распределена равномерно: P s (x) = J-, (5.1) где Ns —количество элементов множества Xs. Функции от s ^ CTA (x)P s (x) и ^ CAS (x)P s (x) (5.2) называются временной и, соответственно, пространственной сложностью в среднем алгоритма A. Более подробно: Определение 5.1. Пусть при любом допустимом значении s множество Xs всех входов размера s является вероятностным пространством, в силу чего временные и пространственные затраты алгоритма A для входов x (т. е. CTА (x) и CSA(x)) размера s являются случайными величинами на Xs. Сложностью в среднем называется математическое ожидание (первая или вторая сумма из (5.2)) соответствующей случайной величины. § 5. Понятие сложности в среднем Сложность в среднем может принимать и нецелые значения, даже если функция затрат целочисленна. Для временной и пространственной сложностив среднем алгоритма A мы будем использовать обозначения T A (0, SA{-). Теорема 5.1. Для любого алгоритма A при любом распределении вероятностей на множестве Xs, где s — некоторое допустимое значение размера \\ ■ \\, сложность в среднем не превосходит сложности в худшем случае: TA (s)sS TA (s), SA(s)^SA(s). Доказательство. Докажем, например, первое неравенство: TA (s) = У CTJx)PJx) s= V (max CAT (x))P s (x) = x <eXs x<e Xs = ^ TA (s)P s (x) = TA(s) J] P s (x) = TA(s). x e Xs x^Xs Второе неравенство доказывается аналогично. □ Ниже в этом параграфе мы рассмотрим временную сложность в среднем ряда алгоритмов. Пример 5.1. Как было уже установлено (пример 4.2), бинарный алгоритм возведения в степень n требует А(n)+А*(n)-2 умножений; если в качестве размера взять m = A(n), то сложность в худшем случае будет равна 2m - 2. Подсчитаем сложность в среднем, привлекая m как размер входа. Всего имеется 2 m -1 неотрицательных целых битовой длины m; если считать все эти числа равновероятными, то искомая сложность есть 2 m -l 2 m -l m - Yt (A(n) + A*(n)-2) = m -2+ m - r ^ A*(n). n=2m-1 n=2m-1 Первая цифра каждого из чисел битовой длины m равна 1; количество чисел, имеющих кроме старшей цифры еще k, 0^k^m-1, ненулевых двоичных цифр, равно f m ) (т. е. числу сочетаний из m - 1 по k). Поэтому искомую сложность можно переписать в виде
Легко проверяется, что при 1 ^ k ^ m - 1 выполнено k-1 Глава 2. Сложность в среднем и возможно дальнейшее упрощение выражения для сложности: m -1 m -2 k =i l =о Если рассматривать m = А(n) как размер входа бинарного алгоритма вычисления an, n eN+, то сложность в среднем по числу умножений для этого алгоритма есть |(m - 1). Таким образом, при больших m сложность в среднем бинарного алгоритма возведения в степень приблизительно равна трем четвертым сложности в худшем случае. Анализ сложности в среднем для широкого ряда арифметических алгоритмов опирается на асимптотический закон распределения простых чисел, который мы приведем без доказательства. Асимптотический закон распределения простых чисел. Для функции п(n), значение которой равно количеству простых чисел, меньших данного натурального n, справедливо асимптотическое равенство я(n)~т n -. (5.3) In n Как следствие, вероятность того, что при выборе «наугад» одного из целых чисел 1,2,..., n попадется простое число, асимптотически 1 1 равна 1—. х ш n Пример 5.2. Вновь вернемся к алгоритму пробных делений, предназначенному для распознавания простоты данного n ^ 2 (примеры 1.2, 4.1). Будем рассматривать в качестве размера входа битовую 1 Предположение о справедливости этого закона распределения простых чисел высказывалось, в частности, Гауссом и Лежандром. Впоследствии в 1850 г. Чебышевым было доказано, что для некоторых констант c и C c—<к{n)<C — для всех достаточно больших n, и, более того, им было установлено, что можно положить C = 1,10555, c = 0,92129. Асимптотическое равенство (5.3) было полностью доказано в 1896 г. независимо Ж.Адамаром и Ш. Валле Пуссеном. «После доказательства неравенств Чебышева в 1850 г. речь шла, казалось бы, только о более точном нахождении и сближении постоянных c и C. Однако асимптотический закон распределения простых чисел был доказан лишь полвека спустя, в самом конце XIX века, на основании совершенно новых идей, предложенных Риманом...» [39]. В [39, гл. V] приводится элементарное доказательство неравенств Чебышева для C = 6 и c = -. Полное доказа- тельство асимптотического закона имеется, например, в [16]. § 5. Понятие сложности в среднем длину т данного числа. На первый взгляд сложность в среднем этого алгоритма могла бы оказаться существенно меньшей, чем сложность в худшем случае, так как для многих входов затраты совсем невелики. Например, для четных входов достаточно одного деления и т. д. Для сложности в худшем случае по числу делений нами была установлена экспоненциальная оценка в(2т/'2). Существует ли d eN такое, что сложность в среднем алгоритма пробных делений как функция от т допускает оценку 0{md)? Мы видим, что для довольно обширного множества входов размера т алгоритм пробных делений работает быстро, и предположение, что для сложности в среднем существует такое число d, выглядит правдоподобным. На самом деле все обстоит не так, потому что среди всех натуральных чисел доля простых (для которых алгоритм пробных делений работает долго) достаточно велика. Оценка количества V{m) простых среди чисел 2т-г ^п<2т может быть получена из приведенной выше теоремы о распределении простых чисел: воспользовавшись тем, что
Дата добавления: 2014-01-11; Просмотров: 740; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |