資料結構›Ch1 演算法基礎第 40 題/共 57 題
40. 遞迴式、Master Theorem、Θ 分析
#DS-01-040中遞迴式Master TheoremΘ 分析
[10%] Assuming that you are a medical information analyst, currently analyzing an algorithm designed to process a 3D MRI volume. The input is a cubic volume of data with side length (total voxels ). Assume is a power of 2.
Pseudo-code:
Surface_Scan(n)
total_intensity = 0
for i = 1 to n
for j = 1 to 100
total_intensity = total_intensity + Read_Pixel(i, j)
return total_intensity
MRI_Voxel_Process(n)
if n <= 1
return
for k = 1 to n
Surface_Scan(n)
for x = 0 to 1
for y = 0 to 1
for z = 0 to 1
MRI_Voxel_Process(n/2)
Note: Assume that the function Read_Pixel(i, j) takes constant time.
Questions:
(1) [3%] Analyze the Surface_Scan(n) function and determine its time complexity using -notation.
(2) [3%] Write down the recurrence relation for the running time of MRI_Voxel_Process(n).
(3) [4%] Analyze the asymptotic growth rate of the algorithm, and determine the overall asymptotic tight bound () for the running time of MRI_Voxel_Process(n). Please write down your calculation process.
📄 成大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎