Предложения для алгоритмического анализа программ Lisp?

Question

Предложения для алгоритмического анализа программ Lisp?

Какие операции в программах языка Common LISP нужно считать достаточно примитивными, чтобы значить единственный "шаг" в алгоритмическом анализе? То, как широко делают современный, шепелявит, варьируются по их реализации?

Конечно, арифметика с маленькими целыми числами рассчитала бы как одноэтапное, но что относительно большего числа? И что относительно того, чтобы рассмотреть различие между reverse и nreverse? А именно, nreverse тета reverse? Что относительно всего массива и операций последовательности? Кроме того, как макросы фигурируют в - как я должен думать о макросах при анализе сложности?

7

algorithm lisp common-lisp

задан Aoriste 27 February 2010 в 20:45

1 ответ

Другие вопросы по тегам:

algorithm lisp common-lisp

Похожие вопросы:

score 9 · Answer 1

Не пытайтесь найти нижний слой однородных «отдельных шагов», просто знайте, что такое O (1), а что нет.
Добавление «больших чисел» ( bignum s) должно быть O (log n), где n - большее из целых чисел. Есть много разных алгоритмов умножения; Я не специалист в этой области, и, скорее всего, это зависит от конкретной реализации.
reverse и nreverse могут быть реализованы O (n) ( reverse с помощью стратегии cdr-input-and-cons-output; nreverse ] путем обмена указателями при cdring). Если я правильно понимаю незнакомый термин «тэта», то да. Обратите внимание, однако, что стандарт CL не дает никаких гарантий относительно временной сложности.
Встроенные операции с последовательностью обычно реализуются путем выбора конкретной реализации для массива или списка в зависимости от типа аргумента, поэтому следует ожидать, что это будет обычный эффективный алгоритм для этого типа данных.
Макросы просто расширяются в другой код. Вы можете посмотреть на их расширение, или увидеть, что они делают в документации, или сделать обоснованное предположение об алгоритме, который использует их расширение. Сложность макрорасширения совершенно не имеет значения (если вы не используете eval / compile , и в этом случае вам также нужно подумать о сложности компилятора реализации), поскольку он запускается во время компиляции - один раз; имеет значение только расширенный код.