Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Янин В.Л. "Новгородские акты XII-XV Хронологический комментарий" (История)

Майринк Г. "Белый доминиканец " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 2" (Художественная литература)

Петров Г.И. "Отлучение Льва Толстого " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 1 " (Художественная литература)
Реклама

Структура и интерпритация компьютерных программ - Абельсон Х.

Абельсон Х. Структура и интерпритация компьютерных программ — М.: Добросвет, 2006. — 608 c.
ISBN 978-5-98227-708-4
Скачать (прямая ссылка): strukturaiinterpretacii2006.pdf
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 269 >> Следующая


58

Глава 1. Построение абстракций с помощью процедур

1.2.3. Порядки роста

Предшествующие примеры показывают, что процессы могут значительно различаться по количеству вычислительных ресурсов, которые они потребляют. Удобным способом описания этих различий является понятие порядка роста (order of growth), которое дает общую оценку ресурсов, необходимых процессу при увеличении его входных данных.

Пусть n — параметр, измеряющий размер задачи, и пусть A(n) — количество ресурсов, необходимых процессу для решения задачи размера n. В предыдущих примерах n было числом, для которого требовалось вычислить некоторую функцию, но возможны и другие варианты. Например, если требуется вычислить приближение к квадратному корню числа, то n может быть числом цифр после запятой, которые нужно получить. В задаче умножения матриц n может быть количеством рядов в матрицах. Вообще говоря, может иметься несколько характеристик задачи, относительно которых желательно проанализировать данный процесс. Подобным образом, A(n) может измерять количество используемых целочисленных регистров памяти, количество исполняемых элементарных машинных операций, и так далее. В компьютерах, которые выполняют определенное число операций за данный отрезок времени, требуемое время будет пропорционально необходимому числу элементарных машинных операций.

Мы говорим, что A(n) имеет порядок роста 0(/(n)), что записывается A(n) = 0(/(n)) и произносится «тета от /(n)», если существуют положительные постоянные kl и k2, независимые от n, такие, что

kl/(n) < A(n) < k2/(n)

для всякого достаточно большого n. (Другими словами, значение A(n) заключено между kl/(n) и k2/(n).)

Например, для линейно рекурсивного процесса вычисления факториала, описанного в разделе 1.2.1, число шагов растет пропорционально входному значению n. Таким образом, число шагов, необходимых этому процессу, растет как 0(n). Мы видели также, чтотребуемый объем памятирастет как 0(n). Для итеративного факториала число шагов по-прежнему 0(n), но объем памяти 0(1) — то есть константа36. Древовиднорекурсивное вычисление чисел Фибоначчи требует 0(ф”) шагов и 0(n) памяти, где ф — золотое сечение, описанное в разделе 1.2.2.

Порядки роста дают всего лишь грубое описание поведения процесса. Например, процесс, которому требуется n2 шагов, процесс, которому требуется 1000n2 шагов и процесс, которому требуется 3n2 + 10n + 17 шагов — все имеют порядок роста 0(n2). С другой стороны, порядок роста показывает, какого изменения можно ожидать в поведении процесса, когда мы меняем размер задачи. Для процесса с порядком роста 0(n) (линейного) удвоение размера задачи примерно удвоит количество используемых ресурсов. Для экспоненциального процесса каждое увеличение размера задачи на единицу будет умножать количество ресурсов на постоянный коэффициент. В оставшейся части раздела 1.2 мы рассмотрим два алгоритма, которые имеют логарифмический порядок ро-

36В этих утверждениях скрывается важное упрощение. Например, если мы считаем шаги процесса как «машинные операции», мы предполагаем, что число машинных операций, нужных, скажем, для вычисления произведения, не зависит от размера умножаемых чисел, а это становится неверным при достаточно больших числах. Те же замечания относятся и к оценке требуемой памяти. Подобно проектированию и описанию процесса, анализ процесса может происходить на различных уровнях абстракции.

1.2. Процедуры и порождаемые ими процессы

59

ста, так что удвоение размера задачи увеличивает требования к ресурсам на постоянную величину.

Упражнение 1.14.

Нарисуйте дерево, иллюстрирующее процесс, который порождается процедурой count-change из раздела 1.2.2 при размене 11 центов. Каковы порядки роста памяти и числа шагов, используемых этим процессом при увеличении суммы, которую требуется разменять?

Упражнение 1.15.

Синус угла (заданного в радианах) можно вычислить, если воспользоваться приближением sin x « x при малых x и употребить тригонометрическое тождество

для уменьшения значения аргумента sin. (В этом упражнении мы будем считать, что угол «достаточно мал», если он не больше 0.1 радиана.) Эта идея используется в следующих процедурах:

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)

(if (not (> (abs angle) 0.1)) angle

(p (sine (/ angle 3.0)))))

а. Сколько раз вызывается процедура p при вычислении (sine 12.15)?

б. Каковы порядки роста в терминах количества шагов и используемой памяти (как функция а) для процесса, порождаемого процедурой sine при вычислении (sine a) ?

1.2.4. Возведение в степень

Рассмотрим задачу возведения числа в степень. Нам нужна процедура, которая, приняв в качестве аргумента основание b и положительное целое значение степени n, возвращает b”. Один из способов получить желаемое — через рекурсивное определение

которое прямо переводится в процедуру

(define (expt b n)

(if (= n 0)

1

(* b (expt b (- n 1)))))

Это линейно рекурсивный процесс, требующий 0(n) шагов и 0(n) памяти. Подобно факториалу, мы можем немедленно сформулировать эквивалентную линейную итерацию:
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 269 >> Следующая