利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn

### 回答1：
对于T(n) = 9T(n/3) + n，nlogba = nlog39，因此logba = log39，由于f(n) = n属于O(nlogba)，所以T(n) = Θ(nlogba) = Θ(nlog39)。
对于T(n) = T(2n/3) + 1，nlogba = log32，因此logba = 1，由于f(n) = 1属于O(1)，所以T(n) = Θ(logn)。
对于T(n) = 3T(n/4) + nlogn，nlogba = nlog43/4，因此logba = log43/4，由于f(n) = nlogn属于O(nlogba)，所以T(n) = Θ(nlog43/4)。

### 回答2：
利用主定理可以方便地求解递归函数的时间复杂度。主定理给出了如下形式的递归方程：T(n) = aT(n/b) + f(n)，其中a ≥ 1, b > 1，f(n)是一个函数。根据主定理，递归函数的时间复杂度可以分为三种情况讨论。

对于第一个递归函数 T(n) = 9T(n/3)，我们可以看出 a = 9，b = 3。根据主定理的情况一，如果 f(n) = O(n^c) 且 logb(a) > c，则 T(n) = Θ(n^logb(a))。对于这个递归函数，f(n) = 0，即 f(n) = O(n^0)。且 log3(9) = 2 > 0，所以根据主定理情况一，这个递归函数的时间复杂度为 Θ(n^2)。

对于第二个递归函数 T(n) = T(2n/3)，我们可以看出 a = 1，b = 3/2。根据主定理的情况二，如果 f(n) = Θ(n^c * log^k(n))，则 T(n) = Θ(n^c * log^(k+1)(n))。对于这个递归函数，f(n) = 1，即 f(n) = Θ(n^0 * log^0(n))。所以根据主定理情况二，这个递归函数的时间复杂度为 Θ(n^0 * log^(0+1)(n)) = Θ(log(n))。

对于第三个递归函数 T(n) = 3T(n/4)，我们可以看出 a = 3，b = 4。根据主定理的情况三，如果 f(n) = Ω(n^c) 且 af(n/b) ≤ kf(n)，其中 k < 1，则 T(n) = Θ(f(n))。对于这个递归函数，f(n) = nlog(n)，根据主定理情况三的条件 af(n/b) ≤ kf(n)，我们可以计算得到 3(n/4)log(n/4) ≤ knlog(n)，整理得到 (3/4)log(n) ≤ (k/4)log(n)。由于 log(n) > 0，所以 (3/4) ≤ (k/4)，即 3 ≤ k。所以根据主定理情况三，这个递归函数的时间复杂度为 Θ(nlog(n))。

### 回答3：
根据主定理，对于一个递归式 T(n) = aT(n/b) + f(n) 的时间函数复杂度，我们可以通过比较函数 f(n) 和 n^log_b(a) 的大小来确定复杂度的近似表达式。其中 a 是递归函数的子问题的数量，b 是每个子问题的规模比例，f(n) 是分解和合并阶段除了递归子问题所需要的时间复杂度。

对于第一个递归式 T(n) = 9T(n/3) + n，我们比较函数 n 和 n^log_3(9)。由于 log_3(9) = 2，因此我们可以得到 n 的复杂度为 O(n^2)。

对于第二个递归式 T(n) = T(2n/3) + 1，我们可以发现每次递归规模都减小了，所以时间复杂度为 O(logn)。

对于第三个递归式 T(n) = 3T(n/4) + nlogn，我们比较函数 nlogn 和 n^log_4(3)。由于 log_4(3) 小于 1，因此我们可以得到 nlogn 的复杂度为 O(nlogn)。