2010-02-27 4 views
7

Common Lisp 프로그램에서 알고리즘 분석에서 단일 "단계"를 계산할만큼 충분히 원시적 인 것으로 간주되는 작업은 무엇입니까? 현대식 술은 얼마나 다양하게 구현됩니까?Lisp 프로그램의 알고리즘 분석을위한 제안?

확실히 작은 정수를 사용한 산술은 단일 단계로 계산되지만 큰 숫자는 무엇입니까? 그리고 reversenreverse의 차이점을 고려하면 어떨까요? 구체적으로는 nreverse 쎄타는 reverse입니까? 모든 배열 및 시퀀스 작업은 어떻습니까? 매크로를 어떻게 해석 할 수 있습니까? 복잡성을 분석 할 때 매크로에 대해 어떻게 생각해야합니까?

+1

질문과 같은 것보다 공황처럼 들린다. –

+0

하하 - 그렇게 의도되지 않았다면, 나는 오늘 아침 그것에 대해 생각하기 시작했고, 나는 그런 것들에 대해서만 추측 할 수 있다는 것을 깨달았다. – Aoriste

답변

9
  • O (1)과 그렇지 않은 것을 모르는 균일 한 "단일 단계"의 하위 계층을 찾으려고하지 마십시오.
  • "더 큰 숫자"(bignums)의 추가는 O (log n)이어야합니다. 여기서 n은 정수 중 큰 값입니다. 곱셈에는 여러 가지 알고리즘이 있습니다. 나는이 분야 전문가가 아니며 구현에 따라 다를 수 있습니다.
  • reversenreverse은 모두 cdr 명령으로 포인터를 교환하여 O (n) (reverse cdr-input-and-cons-output 전략으로 구현할 수 있습니다. 익숙하지 않은 용어 "theta of of"를 올바르게 이해한다면, 그렇습니다. 그러나 CL 표준은 시간 복잡성에 대해 어떠한 보증도하지 않는다는 점에 유의하십시오.
  • 내장 시퀀스 연산은 일반적으로 인수의 유형에 따라 배열 또는 목록 특정 구현을 선택하여 구현되므로 해당 데이터 유형에 대한 일반적인 효율적인 알고리즘이 될 것으로 예상되어야합니다.
  • 매크로는 다른 코드로 확장됩니다. 확장을 보거나 문서화 된 내용을 보거나 확장에 사용되는 알고리즘에 대해 숙련 된 추측을 할 수 있습니다. 매크로 익스텐더의 복잡성은 전혀 상관이 없습니다 (eval/compile을 사용하지 않는 한, 구현시 컴파일러의 복잡성에 대해서도 고려해야합니다). 확장 된 코드 만 중요합니다.
+1

첫 번째 글 머리 기호 +1. –

+0

매우 철저합니다. 고맙습니다. – Aoriste

+0

Theta 표기법은 big-O 표기법과 비슷합니다. 단, 연산 비용이 지정된 표현식의 *와 *보다 아래에 모두 한정된다는 의미입니다. big-O는 "이 연산의 비용이 주어진 함수보다 점차 빠르게 증가하지 않는다"고 말하면서 big-theta는 "이 연산의 비용은 주어진 함수보다 더 빠르게 점진적으로 증가하지도 않고 주어진 함수가 커지지도 않습니다 주어진 함수보다 더 빨리 점근 적으로. " 다시 말해 빅 시타 (big-theta)는 상한뿐만 아니라 성능에 대한 하한을 의미합니다. –

관련 문제