Обобщенный метод анализа не рекурсивных алгоритмов

Дисциплина «Алгоритмы и структуры данных» Лекция № 2 Обобщенный метод анализа не рекурсивных алгоритмов Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Базовые принципы оценки сложности выполнения основных конструкций языков программирования (часть 1) Принципы оценки сложности основных конструкций языков программирования При теоретической оценке временной сложности алгоритма по исходному коду программы будем учитывать и различать следующие особенности алгоритмов • Не рекурсивные алгоритмы – структурное программирование: • Линейная последовательность операторов • Ветвящиеся конструкции (операторы условия if и выбора switch/case) • Циклические конструкции (for, while) • Анализ не рекурсивных подпрограмм (пользовательских функций) • Операторы не структурного программирования • Досрочное завершение циклов (break) • Досрочный переход к следующей итерации (continue) • Оператор безусловного перехода (goto) • Анализ рекурсивного алгоритма Базовые операции Элементарные операции Выберем базовое множество операций (назовем их основными элементарными операциями, так будем полагать, что каждая из них выполняется за один машинный такт, то есть её трудоемкость равна 1 (или более строго – может быть представлена конечным набором машинных команд, не зависящим от входа), число выполнений которых и будет определяться функцией роста трудоемкости алгоритма. Элементарные операции К элементарным (базовым) операциям языка программирования будем относить операции – присваивания (=, +=, -=, *=, /=, %=) – арифметические операции (+, –, *, /, % (получение остатка от деления)); – операции сравнения (>, <, ==, !=, <=, >= ); – логические операции (!, &&, ||); – бинарные операции (~, &, |, ^); – взятие (получение, использование) адреса ячейки памяти: [] – (в массиве), * (разыменовывание), & (получение адреса), -> (указатель на структуру), . (разделитель имени структуры и поля; – вызов и выполнение стандартных библиотечных функций (fabs(), scanf(), printf(),…) количество операций в которых не зависит от входного параметра Базовые операции В ряде случаев при анализе алгоритмов и программ может потребоваться определить количество исполнений строго определенных операций или операторов (например, самых «медленных», ресурсоемких или наиболее характерных для конкретной задачи). В таком случае будем называть такую операцию базовой. Рассмотрим примеры… Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) // +1 s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) // +1 s=s+A[m]; } } } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы на языке программирования 1Б. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); // +1 for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; // +1 for (int j=1; j <= 2*i*n; j++) s=s + A[j]; // +1 for (int k=i; k <= n; k++) { s=s + A[k]; // +1 if (i0) s=s+A[m]; // +1 } } } Сколько раз за время выполнения фрагмента изменялось значение переменной s, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Базовые принципы оценки линейной последовательности операторов Принципы оценки сложности линейных конструкций языков программирования Не рекурсивные алгоритмы: анализ линейных конструкций • Время выполнения операторов присваивания, чтения (ввода) и записи (вывода) обычно имеет порядок О(1), как всякий линейный оператор, кроме случаев использования внутри них функций и процедур. В этом случае оператор имеет порядок выполнения функции или процедуры, если возможно тем или иным образом оценить трудоемкость подпрограммы. • Время выполнения последовательности операторов определяется с помощью правила сумм. Поэтому степень роста времени выполнения последовательности операторов без определения констант пропорциональности совпадает с наибольшим временем выполнения оператора в данной последовательности. Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); О(1)+О(1) = O(max{1, 1,}) = O(1 ) = 1 (в силу рефлексивности О() for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j; j++) s=s + A[j<= 2*i*n]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); О(1)+О(1) = O(max{1, 1,}) = O(1)=O(f(строки кода)) ≠f(N) =1+4 for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j; j++) s=s + A[j<= 2*i*n]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } Базовые принципы оценки ветвящихся процессов Принципы оценки сложности ветвящихся конструкций языков программирования Не рекурсивные алгоритмы: анализ ветвления и выбора Время выполнения условных операторов состоит из • вычисления логического выражения (времени выполнения соответствующих операций) Время вычисления логического выражения обычно имеет порядок О(1), если условие не содержит вызов функций, трудоемкость которых зависит от n – в этом случае проверка условия есть последовательное выполнение элементарных операций, в том числе и используемой в проверке условия функции • выполнения одной из ветвей операторов условия или выбора. Принципы оценки сложности ветвящихся конструкций языков программирования Если конкретную ветвь, которая будет выполнена, определить затруднительно (чувствительность к исходным данным, к проверке условия), то из всех возможных исходов выбирается самый «трудоёмкий», тем самым определяется время работы в худшем, т.е. O(f(N)): • в оператора if – их два: ветвь «да» и ветвь «нет», трудоемкость каждой определяем отдельно, а затем выбираем ту ветвь, функция роста трудоемкости которой имеет бОльший порядок; • в операторе выбора switch анализируется каждая case ветвь, включая ветвь default трудоемкость каждой определяем отдельно, а затем выбираем ту ветвь, функция роста трудоемкости которой имеет бОльший порядок. Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) Чувствителен к исходным данным!!! s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i < n) НЕ чувствителен к исходным данным!!! for (int m=1; m <= n; m++) if (A[m]>0) s=s+A[m]; } } } Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) Чувствителен к исходным данным!!! s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i < n) НЕ чувствителен к исходным данным!!! for (int m=1; m <= n; m++) if (A[m]>0) s=s+A[m]; } } } i= n n i (ложно) 4n Базовые принципы оценки вложенных циклов Принципы оценки сложности циклических конструкций языков программирования Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок О(1), если не содержит внутри себя функцию от n). Часто время выполнения цикла вычисляется, пренебрегая определением констант пропорциональности, как произведение количества выполненных итераций цикла на наибольшее возможное время выполнения операторов тела цикла. Однако, не следует для циклов перемножать число выполняемых итераций на трудоемкость отдельной итерации, так как в этом случае зачастую не верно определяется количество исполняемых операций (вид функции роста), хотя асимптотическая оценка может оказаться верной. Принципы оценки сложности циклических конструкций языков программирования Кроме того, время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно. В случае вложенных циклов, анализ надо начинать оценивания трудоемкость тела цикла «самого внутреннего» цикла. Тогда полученная для него трудоемкость будет использоваться для оценки трудоемкости тела цикла, внешнего относительно рассматриваемого цикла. Так последовательно от внутреннего к самому внешнему циклу можно построить функцию роста. Поскольку каждый из циклов характеризуется суммированием n ( ()) i 1 то для вложенных циклов характерна функция роста вида КОН КОН  (  (...)) i  НАЧ j  НАЧ содержащая несколько вложенных сумм, которые затем необходимо последовательно раскрыть, начиная с самого вложенного. f ( n)  Пример анализа программы с вложенными циклами 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } Пример анализа программы с простым циклом 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } 4𝑛 𝑖=1( 2𝑖𝑛 𝑗=1( ) O(1) ) Определение числа итераций цикла 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( кон ∆ for (int j=1; j <= кон; j+=∆) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; (i0) s=s+A[m]; } } } ( O(1) 𝑗=1 кон j ) ) Определение числа итераций цикла 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( кон ∆ for (int j=1; j <= кон; j+=∆) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; (i0) s=s+A[m]; } } } ( O(1) 𝑗=1 кон j ) ) Определение числа итераций цикла 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( кон ∆ for (int j=нач; j <= кон; j+=∆) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; (i0) s=s+A[m]; } } } ( O(1) 𝑗=нач j ) ) Определение числа итераций цикла 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=нач; j <= кон; j+=∆) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } 4𝑛 𝑖=1( кон ∆ ( O(1) 𝑗=нач ) ) Определение числа итераций цикла 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=нач; j <= кон; j+=∆) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } 4𝑛 𝑖=1( кон ∆ нач 𝑗′= ∆ ) j= ∆ ∗j’ ) ( O(1) Определение числа итераций цикла 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( кон−нач ∆ for (int j=нач; j <= кон; j+=∆) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; (i0) Кон=11 s=s+A[m]; } } } 𝑗′=1 j ) ( O(1) ) Определение числа итераций цикла 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j= <большее>; j <= <меньшее>; j-=∆) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } 4𝑛 𝑖=1( <большее> − <меньшее> ∆ 𝑗′=1 ) ( O(1) ) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } } } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) // +1 s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) // +1 s=s+A[m]; } } } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; } // 4𝑛 𝑖=1( // +1 for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) // +1 s=s+A[m]; } // ) } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j <= 2*i*n; j++) } s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } ) 4𝑛 𝑖=1( // +1 2∗𝑖∗𝑛 𝑗=1 ( ) // +1 // +1 } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int j=1; j <= 2*i*n; j++) s=s + A[j]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } 4𝑛 𝑖=1( // +1 2∗𝑖∗𝑛 𝑗=1 ( ) // +1 // +1 } } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); 4𝑛 for (int i=1; i <= 4*n; i++) 𝑖=1( { if (A[i]>0) // +1 s=s+A[i]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) // +1 s=s+A[m]; } } ) } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", &n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( // +1 𝑛 𝑘=𝑖 ( for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; // +1 ) } } ) ) } Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 90? (Указание: получить формулу f(n) в общем виде для вычисления числа операций) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( // +1 𝑛 𝑘=𝑖 ( for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; // +1 ) } ) } ) } 𝑓 𝑁 = 4𝑛 𝑛 𝑛 (1+ 𝑖=1 𝑘=𝑖 (1+ 𝑚=1(1 ) )) Пример анализа программы, содержащей вложенные циклы 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( // +1 𝑛 𝑘=𝑖 ( for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; // +1 ) } ) } ) } 𝑓 𝑁 = 4𝑛 𝑛 𝑛 (1+ 𝑖=1 𝑘=𝑖 (1+ 𝑚=1(1 ) )) Где неточность (ошибка) подсчета числа операций? Построение эквивалентных преобразования управляющих структур 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( // +1 𝑛 𝑘=𝑖 ( for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; // +1 ) } ) } ) } 𝑓 𝑁 = 4𝑛 𝑛 𝑛 (1+ 𝑖=1 𝑘=𝑖 (1+ 𝑚=1(1 ) 1 i )) n-1 i 4n Построение эквивалентных преобразования управляющих структур 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { for (int i=1; i <= n-1; i++) { if (A[i]>0) s=s+A[i]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; }} 𝑓 𝑁 = ))) 4𝑛 𝑛 𝑛 (1+ (1+ 𝑚=1(1 𝑖=1 𝑘=𝑖 } 1 i for (int i=n; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[i]; for (int k=i; k <= n; k++) { s=s + A[k]; if (i0) s=s+A[m]; } if (A[i]>0) s=s+A[i]; for (int k=i; k <= n; k++) s=s + A[k]; } } } 𝑓 𝑁 = 𝑛−1 𝑛 𝑛 𝑖=1 (1+ 𝑘=𝑖 (1+ 𝑚=1(1)) ) + 1 i n-1 4𝑛 𝑛 𝑖=𝑛(1+ 𝑘=𝑖 (1) ) i 4n Вывод функции роста трудоемкости программы 𝑓 𝑁 = 𝑛−1 𝑛 𝑛 (1+ (1+ 𝑚=1(1)) ) 𝑖=1 𝑘=𝑖 = 𝑛−1 𝑛 (1+ 𝑖=1 𝑘=𝑖 (1+𝑛) ) = 𝑛−1 𝑛 𝑛 (1+ (1) + 𝑖=1 𝑘=𝑖 𝑘=𝑖 ( 𝑛 = 𝑛−1 𝑛 (1+n-i+1 +n 𝑖=1 𝑘=𝑖 1) + = 𝑛−1 𝑖=1 (1+n-i+1 +n(𝑛 = 𝑛−1 2 𝑖=1 ( 2+2n-i +n 1 i + + 4𝑛 𝑖=𝑛(1+1) )= 4𝑛 𝑖=𝑛(1+𝑛 )) + − 𝑖 + 1)= 4𝑛 𝑖=𝑛(1+𝑛 − 𝑖 + 1)= 4𝑛 4𝑛 2+ 𝑖=𝑛 𝑖=𝑛 𝑛 − 4𝑛 𝑖=𝑛 𝑖)= − 𝑖 + 1)) + 2(3n+1) + n(3n+1) − + 𝑛𝑖) + 7n+2 + 3𝑛2 −( n-1 4𝑛 𝑖=1 𝑖 − i 4𝑛 𝑖=𝒏 𝑖= 𝑛−1 𝑖=1 𝑖)= 4n Вывод функции роста трудоемкости программы 𝑛 4𝑛 𝑛 𝑛 𝑓 𝑁 = 𝑛−1 (1+ (1+ (1)) ) + (1+ 𝑚=1 𝑖=1 𝑘=𝑖 𝑖=𝑛 𝑘=𝑖 (1) )= 𝑛 4𝑛 = 𝑛−1 (1+ (1+𝑛) ) + 𝑖=1 𝑘=𝑖 𝑖=𝑛(1+𝑛 − 𝑖 + 1)= 𝑛 𝑛 4𝑛 = 𝑛−1 (1+ (1) + ( 𝑛 )) + 𝑖=1 𝑘=𝑖 𝑘=𝑖 𝑖=𝑛(1+𝑛 − 𝑖 + 1)= 𝑛 4𝑛 4𝑛 4𝑛 = 𝑛−1 (1+n-i+1 +n 1) + 2+ 𝑛 − 𝑖=1 𝑘=𝑖 𝑖=𝑛 𝑖=𝑛 𝑖=𝑛 𝑖= 4𝑛 = 𝑛−1 (1+n-i+1 +n(𝑛 − 𝑖 + 1)) + 2(3n+1) + n(3n+1) − 𝑖=1 𝑖=𝑛 𝑖= 4𝑛 𝑛−1 2 2 = 𝑛−1 ( 2+2n − i +n + 𝑛𝑖) + 7n+2 + 3𝑛 −( 𝑖 − 𝑖=1 𝑖=1 𝑖=1 𝑖)= 𝑛−1 𝑛−1 𝑛−1 𝑛−1 2 𝑛−1 2 2 + 2𝑛 1 − 𝑖 +n 1 + 𝑛 𝑖 + 7n+2 + 3𝑛 𝑖=1 𝑖=1 𝑖=1 𝑖=1 𝑖=1 4𝑛 4𝑛+1 (𝑛−1) 𝑛−1+1 (𝑛−1) 𝑛−1+1 − + =2(n-1)+2n(n-1) − + 𝑛2 (n-1) 2 2 2 𝑛(𝑛−1) 𝑛−1+1 4𝑛 4𝑛+1 (𝑛−1) 𝑛−1+1 2 + + 7𝑛 + 2 +3𝑛 − + = 2 2 2 2 3 2 2 2 𝟑 𝟐 = =2n-2+2𝑛 -2n+1,5𝑛 − 𝑛 − 0,5𝑛 -8𝑛 − 2𝑛=𝟏, 𝟓𝒏 -7,5𝒏 - 𝟐𝒏-2 𝑓 90 =1,5*90*90*90-7,5*90*90-2*90-2=1087243 операций Базовые принципы оценки вложенных циклов с несколькими параметрами, влияющих на трудоемкость Пример анализа программы на языке программирования 2. Пусть дан фрагмент программы int MyF(int f[ ][ ]) { int s=0, n, x; scanf("%d,%d",&x, &n); for (int i=1; i<= 4*n; i++) for (int k=x; k<= x*i; k++) for (int j=1; j<=n*i; j++) s=s + f[i][j]; } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 4𝑛 𝑓 𝑁 = 𝑓 𝑛, 𝑥 =5+ 𝑥∗𝑖 6+ 𝑖=1 𝑛∗𝑖 6+ 𝑘=𝑥 4𝑛 6 𝑗=1 =5+ 𝑥∗𝑖 6+ 𝑖=1 6 + 6𝑛𝑖 = 𝑘=𝑥 4𝑛 6𝑛𝑥𝑖 2 − 6𝑛𝑥𝑖 + 6𝑛𝑖 + 6𝑥𝑖 − 6𝑥 + 12 = 128𝑛4 𝑥 + 48𝑛3 + 40𝑛2 𝑥 + 12𝑛2 + 8𝑛𝑥 + 8𝑛 + 5 =5+ 𝑖=1 𝛩 𝑓 𝑛, 𝑥 = 𝛺 𝑓 𝑛, 𝑥 = 𝛰 𝑓 𝑛, 𝑥 = 𝑛4 𝑥 𝜊(𝑓(𝑛, 𝑥)) = 𝑛5 𝑥 𝜔 𝑓 𝑛, 𝑥 = 𝑛3 𝑥 Пример анализа программы на языке программирования 2. Пусть дан фрагмент программы int MyF(int f[ ][ ]) { int s=0, n, x; scanf("%d,%d",&x, &n); for (int i=1; i<= 4*n; i++) Самостоятельно: for (int k=x; k<= x*i; k++) Есть ли неточность for (int j=1; j<=n*i; j++) (ошибка) при построении s=s + f[i][j]; функции роста? } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 4𝑛 𝑓 𝑁 = 𝑓 𝑛, 𝑥 =5+ 𝑥∗𝑖 𝑛∗𝑖 6+ 𝑖=1 6+ 𝑘=𝑥 4𝑛 6 𝑗=1 =5+ 𝑥∗𝑖 6+ 𝑖=1 6 + 6𝑛𝑖 = 𝑘=𝑥 4𝑛 6𝑛𝑥𝑖 2 − 6𝑛𝑥𝑖 + 6𝑛𝑖 + 6𝑥𝑖 − 6𝑥 + 12 = 128𝑛4 𝑥 + 48𝑛3 + 40𝑛2 𝑥 + 12𝑛2 + 8𝑛𝑥 + 8𝑛 + 5 =5+ 𝑖=1 𝛩 𝑓 𝑁 =𝛺 𝑓 𝑁 =𝛰 𝑓 𝑁 = 𝑛4 𝑥 𝜊(𝑓(𝑛, 𝑥)) = 𝑛5 𝑥 𝜔 𝑓 𝑛, 𝑥 = 𝑛3 𝑥 n^3 или n^2*x = max{n^3, n^2*x} f(N)=n^3 + n^2*x O(f(N))=O(max{n^3, n^2*x} ) 1. x<=n -> n^3 2. x>n -> n^2*x Пример анализа программы на языке программирования 2. Пусть дан фрагмент программы int MyF(int f[ ][ ]) { int s=0, n, x; +1 scanf("%d,%d",&x, &n); +5 for (int i=1; i<= 4*n; i++) +3 for (int k=x; k<= x*i; k++) for (int j=1; j<=n*i; j++) s=s + f[i][j]; } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. ? 4𝑛 𝑓 𝑁 = 𝑓 𝑛, 𝑥 =? + 𝑥∗𝑖 ?+ 𝑖=1 𝑛∗𝑖 ?+ 𝑘=𝑥 4𝑛 ? 𝑗=1 =5+ 𝑥∗𝑖 6+ 𝑖=1 6 + 6𝑛𝑖 = 𝑘=𝑥 4𝑛 6𝑛𝑥𝑖 2 − 6𝑛𝑥𝑖 + 6𝑛𝑖 + 6𝑥𝑖 − 6𝑥 + 12 = 128𝑛4 𝑥 + 48𝑛3 + 40𝑛2 𝑥 + 12𝑛2 + 8𝑛𝑥 + 8𝑛 + 5 =5+ 𝑖=1 𝛩 𝑓 𝑛, 𝑥 = 𝛺 𝑓 𝑛, 𝑥 = 𝛰 𝑓 𝑛, 𝑥 = 𝑛4 𝑥 𝜊(𝑓(𝑛, 𝑥)) = 𝑛5 𝑥 𝜔 𝑓 𝑛, 𝑥 = 𝑛3 𝑥 Пример анализа программы на языке программирования 2. Пусть дан фрагмент программы int MyF(int f[ ][ ]) { int s=0, n, x; // +1 (+3 ?) scanf("%d,%d",&x, &n); // + ? f∊[1..6] = О(1)=1 (рефлексивность О(.)) for (int i=1; i<= 4*n; i++) // +1+2+ (…) Самостоятельно: for (int k=x; k<= x*i; k++) Есть ли неточность for (int j=1; j<=n*i; j++) (ошибка) при построении s=s + f[i][j]; //3 или 4 функции роста? } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 4𝑛 𝑓 𝑁 = 1+? +𝟑 + 𝑥∗𝑖 𝟑+𝟑+ 𝑖=1 𝑛∗𝑖 𝟑+𝟑+ 𝑘=𝑥 4𝑛 (𝟑 + 𝟑) 𝑗=1 =5+ 𝑥∗𝑖 6+ 𝑖=1 6 + 6𝑛𝑖 = 𝑘=𝑥 4𝑛 6𝑛𝑥𝑖 2 − 6𝑛𝑥𝑖 + 6𝑛𝑖 + 6𝑥𝑖 − 6𝑥 + 12 = 128𝑛4 𝑥 + 48𝑛3 + 40𝑛2 𝑥 + 12𝑛2 + 8𝑛𝑥 + 8𝑛 + 5 =5+ 𝑖=1 𝛩 𝑓 𝑛, 𝑥 = 𝛺 𝑓 𝑛, 𝑥 = 𝛰 𝑓 𝑛, 𝑥 = 𝑛4 𝑥 𝜊(𝑓(𝑛, 𝑥)) = 𝑛5 𝑥 𝜔 𝑓 𝑛, 𝑥 = 𝑛3 𝑥 Базовые принципы оценки вложенных циклов с кратным изменением значения счетчика Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( ? 𝑗′=1( for (int j=1; j <= кон; j *= ∆) s=s + A[j]; for (int k=i; k <= n; k++) { } O(1) ) ) } Пусть х – количество итераций цикла, тогда условие завершения цикла: ∆𝒙 > кон x = [log∆(кон)] 1 2 4 8 ∆=2 16 j кон Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( log∆(кон) 𝑗′=1 for (int j=1; j <= кон; j *= ∆) s=s + A[j]; for (int k=i; k <= n; k++) { } ( O(1) ) ) } Пусть х – количество итераций цикла, тогда условие завершения цикла: ∆𝑥 > кон x = [log∆(кон)] 1 2 4 8 ∆=2 16 j кон Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( log∆(кон) ( 𝑗′=1 for (int j=1; j <= кон; j *= ∆) s=s + A[j]; for (int k=i; k <= n; k++) { } O(1) ) ) } 1 2 4 8 16 j кон Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( 𝑙𝑜𝑔∆ кон −𝑙𝑜𝑔∆ нач 𝑗′=1 for (int j=нач; j <= кон; j *= ∆) s=s + A[j]; for (int k=i; k <= n; k++) ( O(1) ) } } ) } 1 2 4 нач=8 16 j кон Пример анализа программы на языке программирования 1А. Пусть дан фрагмент программы: int MyF1(int A[ ]) { int s=0, n; scanf("%d", & n); for (int i=1; i <= 4*n; i++) { if (A[i]>0) s=s+A[i]; 4𝑛 𝑖=1( кон log∆ нач +1 ( 𝑗′=1 for (int j=нач; j <= кон; j *= ∆) s=s + A[j]; for (int k=i; k <= n; k++) O(1) ) } } ) } 1 2 4 нач=8 16 j кон Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n; j=j*2) // j { int k=n-j; do Самостоятельно: { s = s+A[i][i][k]; Есть ли неточность k = k - 3; (ошибка) при построении } while (k > n / 2); } функции роста? }} Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝑛 𝑓 𝑛 =4+ 4+ 𝑖=1 = 4+ 𝛩 𝑓 𝑛 𝑛 𝑖=1 𝑛−𝑗 3 log2 𝑛 8+ 𝑗=1 4 + 2𝑛 log 𝑛 − =𝛺 𝑓 𝑛 4 log2 𝑛 3 𝑛 8 𝑘= =4+ 𝑛 6 4+ 𝑖=1 + 16 log 𝑛 = 2𝑛2 log 𝑛 − =𝛰 𝑓 𝑛 = 𝑛2 log 𝑛 log2 𝑛 𝜊 𝑓 𝑛 2𝑛 − 𝑗=1 4𝑛 log2 𝑛 3 8𝑗 + 16 3 + 16𝑛 log 𝑛 + 4𝑛 + 4 = 𝑛3 𝜔 𝑓 𝑛 = 𝑛2 = Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n; j=j*2;) { int k=n-j; +2 do { s = s+A[i][i][k]; k = k - 3; } while (k > n / 2); } } // j = 1, 2, 4, 8, 16, 32 … 2^j’ // k = n-1, n-2, n-4, n-8, n-16… // j’=1, 2, 3, 4, 5, 6, 7,… log(n) ∆=3 1 Нач = n|2 k n-j кон = n-1 при j=1 Число итераций: (кон – нач)/ ∆ = (кон-нач)/3=кон/3 – нач/3= (n-j)/3 - n/6=(2n-j-n)/6=(n-2*j)/6 Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n; j=j*2;) // j { int k = n - j; do Самостоятельно: { s = s+A[i][i][k]; Есть ли неточность k = k - 3; (ошибка) при построении } while (k > n / 2); } функции роста? }} Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝑛 𝑓 𝑛 =4+ 4+ 𝑖=1 = 4+ 𝛩 𝑓 𝑛 𝑛 𝑖=1 𝑛−𝑗 3 log2 𝑛 8+ 𝑗=1 4 + 2𝑛 log 𝑛 − =𝛺 𝑓 𝑛 4 log2 𝑛 3 𝑛 8 𝑘= =4+ 𝑛 6 4+ 𝑖=1 + 16 log 𝑛 = 2𝑛2 log 𝑛 − =𝛰 𝑓 𝑛 = 𝑛2 log 𝑛 log2 𝑛 𝜊 𝑓 𝑛 2𝑛 − 𝑗=1 4𝑛 log2 𝑛 3 8𝑗 + 16 3 + 16𝑛 log 𝑛 + 4𝑛 + 4 = 𝑛3 𝜔 𝑓 𝑛 = 𝑛2 = Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n; j=j*2;) // j = 1, 2, 4, 8, 16, 32 … { int k=n - j; // k = n-1, n-2, n-4, n-8, n-16… do // j’=1, 2, 3, 4, 5, 6, 7,… log(n) { s = s+A[i][i][k]; k = k - 3; Сделать } while (k > n / 2); замену j = 2j’ } }} Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝐧 𝑓 𝑛 =4+ 4+ 𝐢=𝟏 = 4+ 𝛩 𝑓 𝑛 𝑛 𝑖=1 𝑛−𝑗 3 𝐥𝐨𝐠𝟐 𝒏 8+ 𝑗′=1 4 + 2𝑛 log 𝑛 − =𝛺 𝑓 𝑛 4 log2 𝑛 3 𝑛 8 𝑘= == 4 + 𝑛 6 4+ 𝑖=1 + 16 log 𝑛 = 2𝑛2 log 𝑛 − =𝛰 𝑓 𝑛 log2 𝑛 = 𝑛2 log 𝑛 𝜊 𝑓 𝑛 2𝑛 − 𝑗=1 4𝑛 log2 𝑛 3 8𝑗 + 16 3 + 16𝑛 log 𝑛 + 4𝑛 + 4 = 𝑛3 𝜔 𝑓 𝑛 = 𝑛2 = Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n; j=j*2;) // j = 1, 2, 4, 8, 16, 32 … 2^j’ ….n { int k=n - j; //+2 // k = n-1, n-2, n-4, n-8, n-16… do // j’=1, 2, 3, 4, 5, 6, 7,… log(n) { s = s+A[i][i][k]; // +3 (+2) k = k - 3; // +2 } while (k > n / 2); // +2 } }} Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝑛 𝑓 𝑛 =4+ 4+ 𝑖=1 = 4+ 𝛩 𝑓 𝑛 𝑛 𝑖=1 𝑛−2𝑗′ 3 log2 𝑛 8+ =𝛺 𝑓 𝑛 4 log2 𝑛 3 8 𝑛 𝑘= 6 𝑗′=1 4 + 2𝑛 log 𝑛 − 𝑛 == 4 + 4+ 𝑖=1 + 16 log 𝑛 = 2𝑛2 log 𝑛 − =𝛰 𝑓 𝑛 = 𝑛2 log 𝑛 log2 𝑛 𝜊 𝑓 𝑛 4𝑛 log2 𝑛 3 2𝑛 − 𝑗=1 8𝑗 + 16 3 + 16𝑛 log 𝑛 + 4𝑛 + 4 = 𝑛3 𝜔 𝑓 𝑛 = 𝑛2 = Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n/2; j=j*2;) { int k=n-j; +2 do { s = s+A[i][i][k]; k = k - 3; } while (k > n / 2); } for (int j=n/2; j <= n; j=j*2;) {s = s+A[i][i][k]; k = k – 3;} }} 1 2 4 8 // j = 1, 2, 4, 8, 16, 32 … 2^j’ // k = n-1, n-2, n-4, n-8, n-16… // j’=1, 2, 3, 4, 5, 6, 7,… log(n) // j = 1, 2, 4, 8, 16, 32 … 2^j’ при 2^j’ >= n/2 Тело цикла выполняется 1 раз!!! n|2 k 2^j’ < n/2 n-j n-1 при j=1 Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n; j=j*2;) // j = 1, 2, 4, 8, 16, 32 … 2^j’ { int k=n-j; +2 // k = n-1, n-2, n-4, n-8, n-16… do // j’=1, 2, 3, 4, 5, 6, 7,… log(n) { s = s+A[i][i][k]; +3 (+2) k = k - 3; +2 } while (k > n / 2); +2 } }} Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝑛 𝑓 𝑛 =4+ = 4+ 𝑛 𝑖=1 log2 𝑛 4+ 𝑖=1 ′ 𝑛−2𝑗 −1 3 8+ 𝑗′=1 4 + 2𝑛 log 𝑛 − 4 log2 𝑛 3 𝑛 8 == 4 + 𝑛 𝑘= 6 + 16 log 𝑛 = 2𝑛2 log 𝑛 − 2 log2 𝑛 4+ 𝑖=1 2𝑛 − 𝑗=1 4𝑛 log2 𝑛 3 3 8𝑗 + 16 3 + 16𝑛 log 𝑛 + 4𝑛 + 4 2 = Пример анализа программы на языке программирования 3. Пусть дан фрагмент программы: int myF3(int A[ ][ ][ ]) {int s, n; s=0; scanf("%d", &n); for (int i=1; i <= n; i++) { for (int j=1; j <= n; j=j*2;) { int k=n-j; do { s = s+A[i][i][k]; k = k - 3; } while (k > n / 2); } }} Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. ? ? 𝑓 N =? + ? ?+ 𝑖=1 = 4+ 𝛩 𝑓 𝑛 𝑛 𝑖=1 ?+ 𝑗=1 4 + 2𝑛 log 𝑛 − =𝛺 𝑓 𝑛 ? 𝑛 ? == 4 + 𝑘=? 4 log2 3 𝑛 log2 𝑛 4+ 𝑖=1 + 16 log 𝑛 = 2𝑛2 log 𝑛 − =𝛰 𝑓 𝑛 = 𝑛2 log 𝑛 𝜊 𝑓 𝑛 2𝑛 − 𝑗=1 4𝑛 log2 𝑛 3 8𝑗 + 16 3 + 16𝑛 log 𝑛 + 4𝑛 + 4 = 𝑛3 𝜔 𝑓 𝑛 = 𝑛2 = Базовые принципы оценки сложности выполнения основных конструкций языков программирования (часть 2) Принципы оценки сложности не рекурсивных функций Для программ, содержащих несколько (в том числе и вложенных) функций (среди которых нет рекурсивных), можно подсчитать общее время выполнения программы путем последовательного нахождения времени выполнения процедур, начиная с той, которая не имеет вызовов других функций (на вызов библиотечных функций мы не обращаем, полагая их трудоемкость равно O(1)). Так как мы предположили, что все процедуры нерекурсивные, то должна существовать хотя бы одна процедура, не имеющая вызовов других процедур. Затем можно определить время выполнения процедур, вызывающих эту процедуру, используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этот процесс, найдем время выполнения всех процедур и, наконец, время выполнения всей программы. Принципы оценки сложности не рекурсивных функций Трудоемкость пользовательской функции = • трудоемкость передачи каждого параметра + • трудоемкость выполнения тела функции + • трудоемкость возврата значения через return Принципы оценки сложности не структурных конструкций Анализ фрагментов программ, содержащие операторы безусловного перехода. Операторы безусловного перехода (такие как goto, операторы досрочного выхода из цикла) могут порождать более сложную логическую групповую структуру: • А) Досрочный выход из цикла обычно связан с некоторым условием, тогда оценка определяется по более «длинной» ветви if/else, т.е. по полному выполнению цикла, что значительно ухудшает оценку, если существует большая вероятность досрочного завершения цикла. Принципы оценки сложности не структурных конструкций Анализ фрагментов программ, содержащие операторы безусловного перехода. Операторы безусловного перехода (такие как goto, операторы досрочного выхода из цикла) могут порождать более сложную логическую групповую структуру: • Б) Возврат к предыдущему фрагменту порождает петлю, которая может быть рассмотрена как новая линейная последовательность операторов. Многократное выполнение петли сводится к циклам или рекурентному выполнению вложенных петель. Принципы оценки сложности не структурных конструкций Анализ фрагментов программ, содержащие операторы безусловного перехода. Операторы безусловного перехода (такие как goto, операторы досрочного выхода из цикла) могут порождать более сложную логическую групповую структуру: • В) Отсутствие общего подхода для оценки времени выполнения программы, использующей не приводимое каноническому виду конструкции с использованием оператора GOTO зачастую исключает возможность оценки времени выполнения такого фрагмента. Принципы оценки сложности не структурных конструкций Анализ фрагментов программ, содержащие операторы безусловного перехода. Операторы безусловного перехода (такие как goto, операторы досрочного выхода из цикла) могут порождать более сложную логическую групповую структуру. • В принципе, операторы безусловного перехода можно исключить из программы, заменив их на канонические конструкции структурного программирования. Поэтому при анализе алгоритмов и программ, необходимо построить эквивалентный по очередности фактического выполнения операторов граф потока управления команд. Принципы оценки сложности рекурсивных конструкций Если есть рекурсивные вызовы функции, то с каждым вызовом рекурсивной функции необходимо связать временнУю функцию Т(n), где n – длина входных данных текущего вызова рекурсивной функции. Затем Т(n) представляется как функция на множестве значений T(ki), где ki - фактические значения аргументов, с которыми данная функция рекурсивно вызывается на n-ом шаге Т(n) = F (T(k1), T(k2), …), ki < n, то есть мы получили рекуррентное соотношение для Т(n). Чтобы получить функцию трудоемкости f(n), необходимо решить рекуррентное соотношение, получив аналитическое выражение как функцию от n с учетом начальных условий рекуррентного соотношения, которому соответствует время выполнения функции при условии отсутствия рекурсивного её вызова. Примеры анализа не рекурсивных алгоритмов и программ Пример анализа программы на языке программирования 4. Пусть дана процедура int R(int n); { int i, j; for (int i=2; i<=(2*n); i++) { a[i] = 0; if (i<=n) {a[i]=a[i-1]+i;} } } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 5. Вычислите функцию роста f(n) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании № 4 int myF5() { int t1, t2; R(20); for (t1=1;t1<=10;t1++) { R(t1); for (t2=1;t2<=t1;t2++) R(45); } } Пример анализа программы на языке программирования 4. Пусть дана процедура int R(int n); { int i, j; Самостоятельно: for (int i=2; i<=(2*n); i++) Есть ли неточность { a[i] = 0; (ошибка) при построении if (i<=n) {a[i]=a[i-1]+i;} функции роста? } } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝑛−1 𝑓 𝑛 =4+ 𝑛 11 + 𝑖=1 𝛩 𝑓 𝑛 6 = 4 + 11𝑛 − 11 + 6𝑛 = 𝑖=1 = 17𝑛 − 7 =𝛺 𝑓 𝑛 =𝛰 𝑓 𝑛 𝜊 𝑓 𝑛 = 𝑛2 𝜔 𝑓 𝑛 = 𝑐𝑜𝑛𝑠𝑡 =𝑛 Пример анализа программы на языке программирования 4. Пусть дана процедура int R(int n); { int i, j; Самостоятельно: for (int i=2; i<=(2*n); i++) Есть ли неточность { a[i] = 0; (ошибка) при построении if (i<=n) {a[i]=a[i-1]+i;} функции роста? } } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. ? 𝑛−1 𝑓 𝑛 =4+ 𝑛 11 + 𝑖=1 𝛩 𝑓 𝑛 6 = 4 + 11𝑛 − 11 + 6𝑛 = 𝑖=1 ? = 17𝑛 − 7 =𝛺 𝑓 𝑛 =𝛰 𝑓 𝑛 =𝑛 𝜊 𝑓 𝑛 = 𝑛2 𝜔 𝑓 𝑛 = 𝑐𝑜𝑛𝑠𝑡 Пример анализа программы на языке программирования 4. Пусть дана процедура int R(int n); // +1 (трудоемкость получения значения) { int i, j; for (int i=2; i<=(2*n); i++) // +1+2 { a[i] = 0; if (i<=n) {a[i]=a[i-1]+i;} } } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝑛 𝑓 𝑛 =𝟒+ 2𝑛 11 + 𝑖=2 6 = 4 + 11(𝑛 − 2 + 1) + 6(2𝑛 − 𝑛 + 1 + 1) = 𝑖=𝑛+1 = 4 + 11𝑛 − 11 + 6𝑛 = 𝟏𝟕𝒏 − 𝟕 𝛩 𝑓 𝑛 =𝛺 𝑓 𝑛 =𝛰 𝑓 𝑛 =𝑛 𝜊 𝑓 𝑛 = 𝑛2 𝜔 𝑓 𝑛 = 𝑐𝑜𝑛𝑠𝑡 Пример анализа программы на языке программирования 5. Вычислите функцию роста f(n) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4 int myF5() { int t1, t2; R(20); // fR(N)=𝟏𝟕𝒏 − 𝟕 = 𝒇R(𝟐𝟎) for (t1=1; t1<=10; t1++) { R(t1); // fR(N)=𝟏𝟕𝒏 − 𝟕 = 𝒇R(𝒕𝟏)=17 𝒕𝟏 - 7 // fR(N)=𝟏𝟕𝒏 − 𝟕 = 𝒇R(𝟒𝟓) for (t2=1; t2<=t1; t2++) R(45); } } 10 𝑓 𝑛 = 𝟏𝟕 ∗ 𝟐𝟎 − 𝟕 + 1 + 2 + 𝟏 + 𝟏𝟕𝐭𝟏 − 𝟕 + 𝟐 + 𝟐 + 𝑡1=1 10 = 336 + 𝑡1 (778𝑡1 − 2) = 336 − 2 ∗ 10 + 778 ∗ 𝑡1=1 17 ∗ 45 − 7 + 𝟏 + 𝟐 = 𝑡2=1 10 ∗ (10 + 1) = 42790 + 316 = 43106 2 Пример анализа программы на языке программирования 4Б. Пусть дана процедура int R(int n); { int i, j, x=0; for (int i=2; i<=(2*n); i++) { a[i] = 0; x++; if (i<=n) {a[i]=a[i-1]+i;} } return x; } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 5Б. Вычислите функцию роста f(n) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании № 4 int myF5() { int t1, t2; R(20); for (t1=1;t1<=10;t1++) { if (R(t1) > 5) for (t2=1; t2<=t1; t2++) R(45); } } Пример анализа программы на языке программирования 4Б. Пусть дана процедура int R(int n); { int i, j, x=0; for (int i=2; i<=(2*n); i++) { a[i] = 0; x++; if (i<=n) {a[i]=a[i-1]+i;} } return x; Анализ логики работы функции R(n), показывает, что значение х будет соответствовать количеству итераций цикла, т.е. 2n-1 => x = 2n-1 } 5Б. Вычислите функцию роста f(n), расчет f(n) которой был Вами выполнен в задании № 4 int myF5() { int t1, t2; R(20); for (t1=1;t1<=10;t1++) { if (R(t1) > 5) for (t2=1; t2<=t1; t2++) R(45); } } => 2t1-1 > 5 => t1 > 3 1 3 10 t1 Пример анализа программы на языке программирования 5Б. Вычислите функцию роста f(n), расчет f(n) которой был Вами выполнен в задании № 4 int myF5() { int t1, t2; R(20); for (t1=1;t1<=3;t1++) { (R(t1) > 5) } for (t1=4; t1<=10; t1++) { if (R(t1) > 5) for (t2=1; t2<=t1; t2++) R(45); } } Пример анализа программы на языке программирования 4. Пусть дана процедура int R(int n); { int i, j; Самостоятельно: for (int i=2; i<=(2*n); i++) Есть ли неточность { a[i] = 0; (ошибка) при построении if (i<=n) {a[i]=a[i-1]+i;} функции роста? } } Определите функцию роста f(n) трудоемкости данного алгоритма и её асимптотические оценки ( f(n)), O(f(n)), ( f(n)), o(f(n)), ( f(n)), где n – длина входа. 𝑛−1 𝑓 𝑛 =4+ 𝑛 11 + 𝑖=1 𝛩 𝑓 𝑛 6 = 4 + 11𝑛 − 11 + 6𝑛 = 𝑖=1 = 17𝑛 − 7 =𝛺 𝑓 𝑛 =𝛰 𝑓 𝑛 𝜊 𝑓 𝑛 = 𝑛2 𝜔 𝑓 𝑛 = 𝑐𝑜𝑛𝑠𝑡 =𝑛 Спасибо за внимание!