|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[7] I Математические основы анализа алгоритмов Введение В этой части собраны сведения из математики, которые используются при анализе алгоритмов. Мы советуем бегло просмотреть её и перейти к следующим главам, возвращаясь к просмотренному по мере надобности. В главе 2 мы вводим понятия и обозначения, связанные с асимптотикой функций (в и др.), а также некоторые другие. Наша цель здесь не рассказать о чём-то новом, а просто согласовать обозначения и терминологию. В главе 3 приводятся различные методы вычисления и оценки сумм (подробное изложение можно найти в любом учебнике математического анализа). Глава 4 посвящена преобразованию рекуррентных соотношений в явные оценки. Мы формулируем и доказываем общее утверждение такого рода (теорема 4.1), которого в большинстве случаев оказывается достаточно. Его доказательство довольно длинно, но в дальнейшем не используется, так что при первом чтении его можно пропустить. В главе 5 мы даём определения различных понятий, связанных с множествами, отношениями, функциями, графами и деревьями, и вводим соответствующие обозначения. Глава 6 посвящена основным понятиям комбинаторики и теории вероятностей. Большая часть книги не использует этого материала, так что при первом чтении эту главу (особенно последние разделы) можно смело пропустить, возвращаясь к пропущенному по мере надобности. 2Скорость роста функций Сравнивая два алгоритма сортировки в главе 1, мы установили, что время работы одного (сортировка слиянием) примерно пропорционально га2, а другого (сортировка вставками) - ralgra. Каковы бы ни были коэффициенты пропорциональности, для достаточно больших га первый алгоритм работает быстрее. Анализируя алгоритм, можно стараться найти точное число выполняемых им действий. Но в большинстве случаев игра не стоит свеч, и достаточно оценить асимптотику роста времени работы алгоритма при стремлении размера входа к бесконечности (asymptotic efficiency). Если у одного алгоритма скорость роста меньше, чем у другого, то в большинстве случаев он будет эффективнее для всех входов, кроме совсем коротких. (Хотя бывают и исключения.) 2.1. Асимптотические обозначения Хотя во многих случаях эти обозначения используются неформально, полезно начать с точных определений. 0-обозначение В главе 2 мы говорили, что время Т(п) работы алгоритма сортировки вставками на входах длины га есть 0(га2). Точный смысл этого утверждения такой: найдутся такие константы с\, с2 > 0 и такое число по, что cira2 Т(п) с2га2 при всех га щ. Вообще, если д(п) - некоторая функция, то запись /(га) = Q(g(n)) означает, что найдутся такие с\, с2 > 0 и такое гао, что 0 с\д{п) f(n) с2д(га) для всех га гао (см. рис. 2.1). (Запись /(га) = Q(g(n)) читается так: «эф от эн есть тэта от же от эн».) [!!!!!!!!! Рисунок 2.1 - подпись к нему: ] Иллюстрации к определениям /(га) = Q(g(n)), /(га) = 0(д(п)) и f(n) = Q(g(n)). Разумеется, это обозначение следует употреблять с осторожностью: установив, что /i(ra) = Q(g(n)) и /2(га) = Q(g(n)), не следует |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||