資料結構›Ch1 演算法基礎
第 40 題/共 57 題
◀ DS 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 nn (total voxels =n×n×n= n \times n \times n). Assume nn 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 Θ\Theta-notation.

(2) [3%] Write down the recurrence relation for the running time T(n)T(n) of MRI_Voxel_Process(n).

(3) [4%] Analyze the asymptotic growth rate of the algorithm, and determine the overall asymptotic tight bound (Θ\Theta) for the running time of MRI_Voxel_Process(n). Please write down your calculation process.

📄 成大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎
本章題號 · 21–40 / 57