資料結構›Ch1 演算法基礎
第 53 題/共 57 題
◀ DS 53/57
53. Recurrence、Master Theorem、Time Complexity
#DS-01-053中RecurrenceMaster TheoremTime Complexity

In the following procedure P, P and B are both procedures; each statement line in and outside the loop counts 1 step.

Procedure P(array1[a1, a2, ..., an])
1. if n<9 exit.
2. call B(array1[a1, a2, ..., an])
   declare new empty array2, array3, array4;
3. for (i=1 to n)
4. { if ((i mod 9)=1)   insert ai into array2;
5.   if ((i mod 9)=4)   insert ai into array3;
6.   if ((i mod 9)=7)   insert ai into array4 }
8. call P( array2 );
9. call P( array3 );
10. call P (array4);

In order to make P's complexity O(n)O(n), which of the following can be B's complexity? (mm is the input size of B)

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