Программист-прагматик. Путь от подмастерья к мастеру

ОглавлениеДобавить в закладки К обложке

• Те, кто интересуется данным предметом более глубоко (по сравнению с его подачей в книге Седжвика), могут прочесть каноническую серию книг Дональда Кнута "Искусство программирования", в которых анализируются разнообразные алгоритмы [Knu97a, Knu97b, Ктш98].

• В упражнении 34 рассматривается сортировка массивов, состоящих из чисел типа "длинное целое". Как скажутся на сортировке усложнение ключей и издержки на их сравнение? Оказывает ли структура ключей влияние на эффективность работы алгоритмов сортировки, словом, является ли самый быстрый алгоритм сортировки таковым во всех случаях?

Упражнения

34. Авторы книги составили набор простых программ сортировки, которые можно загрузить с их Интернет-сайта (www.pragmaticprogrammer.com). Прогоните эти программы на разных компьютерах, имеющихся в вашем распоряжении. Соответствуют ли полученные вами данные ожидаемым кривым? Какие заключения можно сделать об относительных скоростях ваших машин? Каково влияние различных установочных параметров компиляторов? Является ли поразрядная сортировка действительно линейной? (Ответ см. в Приложении В.)

35. Приведенная ниже подпрограмма выводит на печать содержимое двоичного дерева. Предполагая, что дерево сбалансировано, какой (примерно) объем стека будет использоваться подпрограммой для вывода на печать дерева, состоящего из 1000000 элементов? (Предполагается, что вызовы подпрограммы не оказывают существенной нагрузки на стек). (Ответ см. в Приложении В.)

void printTree(const Node *node) {

char buffer[1000];

 if (node) {

   printTree(node->left);

   getNodeAsString(node, buffer);

   puts(buffer);

   printTree(node->right);

 }

}

36. Существует ли способ уменьшить потребность подпрограммы, описанной в упражнении 35, в ресурсах стека (помимо уменьшения размера буфера)? (Ответ см. в Приложении В.)

37. В разделе "Оценка с точки зрения здравого смысла" утверждается, что алгоритм двоичного поиска является O(lg(n)). Можно ли это доказать? (Ответ см. в Приложении В.)


-= 164 =-
Регистрация.
Забыли пароль?
Логин
Пароль
Запомнить меня