匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 6 年前

求助資料結構的遞迴及時間複雜度

(A) Consider the following C program of a recursive function:

void f(int n)

{

int i;

if (n>1) {

for (i=1; i<=n; i++) {

printf("Computer Science.\n");

}

f(n/2);

f(n/2);

}

}

(a)How many lines does the program print if we call f(1024)?

(b)Write a recurrence relation for the time complexity.

(c)How many lines, as a function of n in form, does the program print? Assume n is a power of 2.

1 個解答

評分
  • sponge
    Lv 6
    6 年前
    最佳解答

    (a)

    如果 n>1, 它會印出 n 行後呼叫兩次 f(n/2)

    f(1024) 印出 1024 行後呼叫二次 f(512)

    每個 f(512) 印出 512 行後呼叫二次 f(256)

    因為有兩次呼叫 f(512), 所以會印出 2*512 行且產生四個呼叫 f(256)

    f(256) 這邊類推,印出 4*256 行且產生八次呼叫 f(128)

    f(128) 共印出 8*128 行且產生 16 次呼叫 f(64)

    f(64) 共印出 16*64 行且產生 32 次呼叫 f(32)

    f(32) 共印出 32*32 行且產生 64 次呼叫 f(16)

    f(16) 共印出 64*16 行且產生 128 次呼叫 f(8)

    f(8) 共印出 128*8 行且產生 256 次呼叫 f(4)

    f(4) 共印出 256*4 行且產生 512 次呼叫 f(2)

    f(2) 共印出 512*2 行且產生 1024 次呼叫 f(1)

    f(1) 因為違反 n>1 就不執行 if, 也不遞迴呼叫

    總計: 1024+2*512+4*256+8*128+16*64+32*32+64*16+128*8+256*4+512*2 = 10240 行

    (b)

    用 T(n) 表示 f(n) 的時間複雜度

    f(n) 內迴圈被執行 n 次,外加兩次 f(n/2)

    迴圈部分時間複雜度就是 n, 兩次 f(n/2) 時間複雜度為 2*T(n/2)

    因此遞迴關係: T(n) = n + 2*T(n/2)

    (c)

    將 T(n) 持續展開:

    T(n)

    = n + 2*T(n/2)

    = n + 2*(n/2) + 4*T(n/4)

    = n + 2*(n/2) + 4*(n/4) + 8*T(n/8)

    = ...

    因為 n 是二的次方,令 n = 2^m, m = log2(n)

    對剛才的展開式追蹤展開 i 次的結果

    T(n)

    = n + 2*T(n/2), i=1

    = 2n + 4*T(n/4), i=2

    = 3n + 8*T(n/8), i=3

    = ...

    = in + 2^i*T(n/2^i), 展開第 i 次

    當 i=m, 展開成

    = mn + 2^m*T(n/2^m)

    = mn + 2^m*T(n/n)

    = mn + 2^m*T(1)

    f(1) 不印出任何東西,故這題可直接作 T(1)=0

    所以共印出 mn = n*log2(n) 行

    希望如上回答對您有幫助!

還有問題?馬上發問,尋求解答。