|
|||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[3] тов копируется указатель на данные, составляющие этот объект, а сами поля объекта - нет. Например, если х - параметр процедуры, то присваивание х <- у, выполненное внутри процедуры, снаружи заметить нельзя, а присваивание f[x] <- 3 - можно. Упражнения 1.1-1 Следуя образцу рис. 1.2, покажите, как работает Insertion-Sort на входе А = (31,41, 59, 26,41,58). 1.1-2 Измените процедуру Insertion-Sort так, чтобы она сортировала числа в невозрастающем порядке (вместо неубывающего). 1.1-3 Рассмотрим следующую задачу поиска: Вход: Последовательность га чисел А = (а\, ci2, ., ап) и число v. Выход: Индекс г, для которого v = A[i], или специальное значение nil, если v не встречается в А. Напишите программу линейного поиска (linear search), который последовательно просматривает А в поисках v. 1.1-4 Даны два га-значных двоичных числа, записанных в виде га-элементных массивов А и В. Требуется поместить их сумму (в двоичной записи) в (га+ 1)-элементный массив С. Уточните постановку задачи и запишите соответствующую программу на псевдокоде. 1.2. Анализ алгоритмов Рассматривая различные алгоритмы решения одной и той же задачи, полезно проанализировать, сколько вычислительных ресурсов они требуют (время выполнения, память), и выбрать наиболее эффективный. Конечно, надо договориться о том, какая модель вычислений используется. В этой книге в качестве модели по большей части используется обычная однопроцессорная машина с произвольным доступом (random-access machine, RAM), не предусматривающая параллельного выполнения операций. (Мы рассмотрим некоторые модели параллельных вычислений в последней части книги.) Сортировка вставками: анализ Время сортировки вставками зависит от размера сортируемого массива: чем больше массив, тем больше может потребоваться времени. Обычно изучают зависимости времени работы от размера входа. (Впрочем, для алгоритма сортировки вставками важен не только размер массива, но и порядок его элементов: если массив почти упорядочен, то времени требуется меньше.) Как измерять размер входа (input size)? Это зависит от конкретной задачи. В одних случаях разумно считать число элементов на входе (сортировка, преобразование Фурье). В других более естественно считать общее число битов, необходимое для представления всех входных данных. Иногда размер входа измеряется не одним числом, а несколькими (например, число вершин и число рёбер графа). Временем работы (running time) алгоритма мы называем число элементарных шагов, которые он выполняет - вопрос только в том, что считать элементарным шагом. Мы будем полагать, что одна строка псевдокода требует не более чем фиксированного числа операций (если только это не словесное описание какой-то сложной операции - типа «отсортировать все точки по ж-координате»). Мы будем различать также вызов (call) процедуры (на который уходит фиксированное число операций) и её исполнение (execution), которое может быть долгим. Итак, вернёмся к процедуре Insertion-Sort и отметим около каждой строки её стоимость (число операций) и число раз, которое эта строка исполняется. Для каждого j от 2 до га (здесь га = length[A] - размер массива) подсчитаем, сколько раз будет исполнена строка 5, и обозначим это число через tj. (Заметим, что строки внутри цикла выполняются на один раз меньше, чем проверка, поскольку последняя проверка выводит из цикла.) Insertion-Sort(A)стоимость число раз
Строка стоимости с, повторённая т раз, даёт вклад cm в общее число операций. (Для количества использованной памяти этого сказать нельзя!) Сложив вклады всех строк, получим п Т(п) = cin + с2(га - 1) + с4(га - 1) + с5+ J = 2 п п + се J>j " !) + с7J>j - 1) + с8(п - 1). j = 2j = 2 Как мы уже говорили, время работы процедуры зависит не только от га, но и от того, какой именно массив размера га подан ей на вход. Для процедуры Insertion-Sort наиболее благоприятен случай, когда массив уже отсортирован. Тогда цикл в строке 5 завершается после первой же проверки (поскольку A[i] key при г = j - 1), так что все tj равны 1, и общее время есть Г(га) = сгп + с2(га - 1) + с4(га - 1) + с5(га - 1) + с8(га - 1) = = (ci + с2 + с4 + с5 + с8)га - (с2 + с4 + с5 + с8). Таким образом, в наиболее благоприятном случае время Т(п), необходимое для обработки массива размера га, является линейной функцией (linear function) от га, т.е. имеет вид Т{п) = an + Ь для некоторых констант а и Ь. (Эти константы определяются выбранными значениями с\,..., с8.) Если же массив расположен в обратном (убывающем) порядке, время работы процедуры будет максимальным: каждый элемент A[j] придётся сравнить со всеми элементами А[1] .. .A[j - 1]. При этом tj = j. Вспоминая, что (см. гл. 3), получаем, что в худшем случае время работы процедуры равно Теперь функция Т(п) - квадратичная (quadratic function), т.е. имеет вид Т(п) = an2 + Ъп + с. (Константы а, Ъ и с снова определяются значениями ci-c8.) - (с2 + с4 + с5 + с8) |
Среды: 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 | |||||||||||||||||||||||||||||||||||||||||||||