ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Асимптотический анализ Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных. - презентация

1 ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Асимптотический анализ Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ОСНОВЫ ПРОГРАММИРОВАНИЯ

2 Математический аппарат © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Для упрощения сумм можно воспользоваться следующими формулами ( где А, B и C – независящая от i константы):

3 Математический аппарат © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 Задача 1.1 Типичный калькулятор умеет вычислять натуральные логарифмы (по основанию e) и логарифмы по основанию 10. Как с помощью этих операций вычислить log 27 59, log 15 40? a) b) c) d) e) f) Задача 1.2 Найдите эквивалентное представление следующих выражений, не содержащее знака суммы:

4 Асимптотические соотношения © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Пусть f и g– положительные функции от n.Тогда: 1. f(n) = O(g(n)) g(n) = Ω(f(n)). 2. f(n) = Θ(g(n)) g(n) = Θ(f(n)). 3. f(n) = Θ(g(n)) [ f(n) = O(g(n)) и f(n) = Ω(g(n)) ]. 4.f(n) = o(g(n)) g(n) = ω(f(n) ). 5.f(n) = o(g(n)) 6.f(n) = ω(g(n)) 7. f(n) = o(g(n)) f(n) = O(g(n)), обратное не верно. 8.f(n) = ω(g(n)) f(n) = Ω(g(n)), обратное не верно. 9.f(n) ограничено сверху и снизу положительными константами тогда и только тогда, когда f(n) = Θ(1).

5 Асимптотические соотношения. (пример 1) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 Докажем следующее асимптотическое соотношение: f(n) = O(g(n)) g(n) = Ω(f(n)). Дано: f(n) = O(g(n)). Доказательство: По определению из того, что f(n) = O(g(n)) следует, что: Данное неравенство можем переписать в виде: Отсюда, обозначив, получаем: Дано: g(n) = Ω(f (n)). Доказательство: По определению из того, что g(n) = Ω(f(n)) следует, что: Аналогично предыдущему доказательству, обозначим через, тогда

6 Асимптотические соотношения. (пример 2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 Докажем следующее асимптотическое соотношение: f(n) = o(g(n)) Дано: f (n) = o(g(n)). Доказательство: По определению из того, что f (n) = o(g(n)) следует, что: Отсюда перейдем к следующему предельному соотношению: Чем больше значение константы c, тем больше вероятность того, что найдется такое n 0,при котором неравенство (*) выполняется. Таким образом, интерес представляют малые значения c. Перепишем последний предел в виде:

7 Асимптотические соотношения. (пример 2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Докажем следующее асимптотическое соотношение: f (n) = o(g(n)) Дано: Доказательство: Поскольку предел функции h(n)= f (n)/g(n) равен 0, значит эта функция является бесконечно малой. То есть f (n) растет медленнее, чем g(n), а значит найдется такое положительное n 0, что для любой положительной константы c, будет выполняться неравенство:

8 Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Задача 2.1 а) f 1 (n) = lg n, f 2 (n) = n

9 Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 Задача 2.1 b) f 1 (n) = n, f 2 (n) = nsin(n)

10 Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 Задача 2.1 c) f 1 (n) = n lg c, f 2 (n) = n lgn

11 Визуально определить асимптотические отношения между функциями © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 Задача 2.1 d) f 1 (n) = n!, f 2 (n) = n n

12 Правило Лопиталя © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 Теорема Лопиталя если f (x) и g(x) удовлетворяют следующим условиям: 1. f (x) и g(x) дифференцируемы в окрестности a за исключением, быть может, самой точки a (в проколотой окрестности a). 2. g'(x) 0 в проколотой окрестности a На практике данная теорема полезна при вычислении пределов с логарифмами: т.к. [ln(x)]' = 1/x., то логарифм легко свести к полиному, для которых пределы вычислять значительно проще.

13 Определение асимптотических соотношений с помощью пределов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 a) b) c) d) e) f) Задача 2.2 Для каждой из приведенных ниже пар функций f и g выполняется одно из неравенств: либо f = O(g), либо g= O( f ), но не оба сразу. При помощи пределов определите, какой из случаев имеет место.

14 Определение асимптотических соотношений с помощью пределов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 f1(n)f1(n)f2(n)f2(n)OΩΘ nn2n2 lg nn 2n2n 2 n/2 n lg c n lg n n!n!n nn sin n lg(n!)lg(n n ) ax 2 +bxx2x2 lg n = log 2 n n! = 123 … n Задача 2.3 Заполнить таблицу

15 Определение асимптотических соотношений с помощью пределов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 Расположите по возрастанию : a) log n, log(log n), n b) n!, (1/3) n, log 2 n c) 4, (1/3) n, d), log 2 n, (3/2) n e) 4, (1/3) n, (3/2) n Задача 2.4

16 Определение асимптотических соотношений с помощью пределов* © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 Задача 2.5 Используйте O, o, ω, и Θ для описания отношений между следующими парами функций: a)log k n, n, где k >0 - константа b)n k, c n, где k >0, с>1 – константы c) 2 n, 2 n/2 * Дополнительные задания

17 Доказательство асимптотических соотношений © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 Задача 3.1 a) Докажите, что 17n 1/6 = O(n 1/5 ) Задача 3.2* Докажите или опровергните каждое из следующих утверждений: a) f (n) = O(g(n)) g(n) = o(f (n)). b) f(n) + g(n) = (max(f(n), g(n)). c) f (n) = O(f 2 (n)). d) f (n) = O(g(n)) Ω(f (n)) * Дополнительные задания

18 Литература © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 1.(CLRS) Кормен Т., Лейзерсон Ч., Ривест Р. Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. – М.: Издательский дом "Вильямс", – 1296 с.: ил. – Парал. тит. англ. ISBN 978–5–8459–0857–5. 2.Дж. Макконнел Анализ алгоритмов. Активный обучающий подход (3-е дополненное издание). – М.: Техносфера, – 416 с. 3.Миллер Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер; Пер. с англ. – М.: БИНОМ. Лаборатория знаний, – 406 с.