Ответы на экзаменационные вопросы. Введение
Скачать 389.99 Kb.
|
5.3. Трудоемкость основных алгоритмических конструкцийДля получения функции трудоемкости алгоритма, уточним понятия «элементарных» операций, соотнесенных с языком высокого уровня. В качестве таких «элементарных» операций предлагается использовать следующие: 1) Простое присваивание: а:= b; 2) Одномерная индексация a[i] : (адрес (a)+i*длина элемента); 3) Арифметические операции: (*, /, -, +); 4) Операции сравнения: a < b; 5) Логические операции: (l1)or (l2), (l1)and (l2), not(l1). После введения элементарных операций анализ трудоемкости основных алгоритмических конструкций в общем виде сводится к следующим положениям: 1) Конструкция «Следование» f1 Трудоемкость конструкции есть сумма  трудоемкостей блоков, следующих друг за другом. f2 F «следование» = f1+ … +fk, где k – количество блоков. B) Конструкция «Ветвление»  if (l1 ) thenfthen с вероятностью p elsefelse с вероятностью (1-p) Общая трудоемкость конструкции «Ветвление» требует анализа вероятности выполнения переходов на блоки «Then» и «Else» и определяется как: F «ветвление» = fthen *p + felse * (1-p).  C) Конструкция «Цикл»for i := 1 to N  f Û end После сведения конструкции к элементарным операциям ее трудоемкость определяется как: F «цикл» = 1+N*(3+f«тела цикла») Примеры анализа простых алгоритмовПример 1 Задача суммирования элементов квадратной матрицы SumM (A, n; Sum) Sum := 0 For i := 1 to n For j := 1 to n Sum := Sum + A[i,j] end for Return (Sum) End Алгоритм выполняет одинаковое количество операций при фиксированном значении n, и следовательно является количественно-зависимым. Применение методики анализа конструкции «Цикл » дает: FA(n)= 1+1+ n *(3+1+ n *(3+4))=7 n2+4* n +2 = Q(n2), заметим, что под n понимается линейная размерность матрицы, в то время как на вход алгоритма подается n 2 значений. Пример 2 Задача поиска максимума в массиве MaxS (S,n; Max) Max := S[1] For i := 2 to n if Max < S[i] then Max := S[i] end for return Max End 1+(1+3n) Данный алгоритм является количественно-параметрическим, поэтому для фиксированной размерности исходных данных необходимо проводить анализ для худшего, лучшего и среднего случая. 1). Худший случай Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна: FA^(n)=1+1+1+ (n-1) (3+2+2)=7n - 4 = Q(n). 2) Лучший случай Минимальное количество переприсваивания максимума (ни одного на каждом проходе цикла) будет в том случае, если максимальный элемент расположен на первом месте в массиве. Трудоемкость алгоритма в этом случае равна: FA(n)=1+1+1+ (n-1) (3+2)=5n - 2 = Q(n). В) Средний случай Алгоритм поиска максимума последовательно перебирает элементы массива, сравнивая текущий элемент массива с текущим значением максимума. На очередном шаге, когда просматривается к-ый элемент массива, переприсваивание максимума произойдет, если в подмассиве из первых к элементов максимальным элементом является последний. Очевидно, что в случае равномерного распределения исходных данных, вероятность того, что максимальный из к элементов расположен в определенной (последней) позиции равна 1/к. Тогда в массиве из n элементов общее количество операций переприсваивания максимума определяется как:  Величина Hn называется n-ым гармоническим числом. Таким образом, точное значение (математическое ожидание) среднего количества операций присваивания в алгоритме поиска максимума в массиве из n элементов определяется величиной Hn (на бесконечности количества испытаний), тогда: FA(n)=1 + (n-1) (3+2) + 2 (Ln(n) + )=5 n +2 Ln(n) - 4 +2 = Q(n). |
Похожие:
 | Ответы на экзаменационные вопросы по истории. Вопросы и ответы на экзаменационные вопросы по истории. | | Экзаменационные вопросы по культурологии А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные вопросы с ответами по физкультуре Вопросы и ответы к теоретической части экзамена по физкультуре | | Ответы на экзаменационные вопросы по литературе для 9 класса Вопросы из вариантов I и II (общеобразовательная школа, 31 и 21 билет соответственно; "старые", "Вестник образования" №4 февраль... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... Биология урок, тест, ответы, билеты, биология человека, общая биология, егэ 2006, школа, олимпиада, тестирование биология, экзамен,... |  | Экзаменационные вопросы по бжд для студентов специальности 110203.... Экзаменационные вопросы по бжд для студентов специальности 190603. 65 – «Сервис транспортных и технологических машин и оборудования... |
| Экзаменационные вопросы по нормальной физиологии Содержит ответы на 143 экзаменационных вопроса по охране труда, а также курсы лекций по охране труда | | Экзаменационные вопросы по истории и философии науки Курс «История и философия науки» Программы курса и экзаменационные вопросы по первым двум частям курса представлены ниже |
| Экзаменационные билеты по истории России (9 класс) Девятиклассники!... Билет № Вопрос Древняя Русь в IX – начале XII в.: возникновение государства, древнерусские князья и их деятельность | | Экзаменационные вопросы интернет-курсов интуит (intuit): 192. Введение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования |
| Экзаменационные вопросы интернет-курсов интуит (intuit): Введение... Анооспо «Оренбургский колледж менеджмента, туризма и гостиничного сервиса» (техникум) | | Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... | | Содержание введение Глава I. Из истории создания религиозных учебных заведений А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты по литературе для 9 класса Билет №1 «Слово о полку Игореве» На этапе окончания основной школы девятиклассники, выбравшие экзамен по литературе, сдают его, как правило, в устной форме (собеседование,... | | Ответы на экзаменационные вопросы интернет-курсов интуит (intuit): 138. Микроэкономика фирмы Администрация региона Х ввела запрет на вывоз бананов со своей территории (бананы – главный продукт потребления жителей региона).... |
