트리를 리스트로 변환하는 프로시저의 시간 복잡도 문제입니다. 언어는 scheme입니다.

Question

(define (tree->list-1 tree) (if (null? tree) '() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree) (define (copy-to-list tree result-list) (if (null? tree) result-list (copy-to-list (left-branch tree) (cons (entry tree) (copy-to-list (right-branch tree) result-list))))) (copy-to-list tree '())) 두 프로시저 모두 이진 트리를 인자로 받아서 리스트로 반환해주는 프로시저입니다.두 프로시저 모두 이진 트리의 엔트리를 고른 뒤, (왼쪽 가지, 엔트리, 오른쪽 가지) 순으로 병합하는 것을 반복해서 리스트를 반환하는 구조입니다.그런데 첫번째 프로시저는 병합하는 수단으로 append 프로시저를 사용하고 두번째 프로시저는 병합하는 수단으로 cons를 사용합니다. 이 차이가 프로시저의 시간복잡도 차이를 만듭니다. 여기까지는 이해했습니다. 그런데 결국 시간복잡도를 어떻게 구하는 지를 잘 모르겠습니다. append의 시간복잡도는 Θ(n)이고, cons의 시간복잡도는 Θ(1)인데, 왜 1번 프로시저의 시간 복잡도는 Θ(n log n)이 되고,2번 프로시저의 시간 복잡도는 Θ(n)이 되는지 이해하지 못했습니다.부디 한번 고민해 주시면 감사하겠습니다.

트리를 리스트로 변환하는 프로시저의 시간 복잡도 문제입니다. 언어는 scheme입니다.

0개의 답변

Q&A 목록