資料結構›Ch1 演算法基礎第 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 , which of the following can be B's complexity? ( is the input size of B)
📄 中央114
▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎