Giáo trình hướng dẫn kĩ thuật phân tích đánh giá giải thuật theo phương pháp tổng quan p3

Ðây là phương trình đệ quy để tính thời gian thực hiện của chương trình đệ quy Giai_thua. Ví du 1-11: Chúng ta xét thủ tục MergeSort một cách phác thảo như sau:FUNCTION MergeSort (L:List; n:Integer):List; VAR L1,L2:List; BEGIN IF n=1 THEN RETURN(L) ELSE BEGIN Chia đôi L thành L1 và L2, với độ dài n/2; RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2))); END; END;
Nội dung trích xuất từ tài liệu:
Giáo trình hướng dẫn kĩ thuật phân tích đánh giá giải thuật theo phương pháp tổng quan p3 h a n g e Vi h a n g e Vi XC XC e e F- F- w wPD PD er er ! ! W W O O N N y y bu bu Giải thuật Kĩ thuật phân tích giải thuật to to k k lic lic C Cw w m m w ww w o o .c .c .d o .d o c u -tr a c k c u -tr a c k C1 nêu n = 0 T(n) = T(n - 1) + C 2 nêu n > 0 Ðây là phương trình đệ quy để tính thời gian thực hiện của chương trình đệ quy Giai_thua. Ví du 1-11: Chúng ta xét thủ tục MergeSort một cách phác thảo như sau: FUNCTION MergeSort (L:List; n:Integer):List; VAR L1,L2 ...