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

### 回答1：
对于第一个问题，根据主定理，可以得到T(n) = Θ(nlog3 9)，即O(n2.81)。

对于第二个问题，根据主定理，可以得到T(n) = Θ(log2/3n)，即O(logn)。

对于第三个问题，根据主定理，可以得到T(n) = Θ(nlog4/3 3)，即O(n1.395)。

### 回答2：
利用主定理可以帮助我们确定以上三个递归时间函数的复杂度。

首先，主定理是一个关于递归时间复杂度的定理，适用于形如T(n) = aT(n/b) + f(n)的递归式，其中a≥1，b>1是常数，f(n)是一个渐进正函数。

对于第一个时间函数T(n) = 9T(n/3) + n，a = 9，b = 3，f(n) = n。我们比较f(n)与n^log_b(a)的大小，即n和3^2的大小，可以看出f(n) = n的增长速度大于n^2，所以f(n) = n，根据主定理的第三种情况，时间复杂度为O(n^log_b(a)) = O(n^2)。

对于第二个时间函数T(n) = T(2n/3) + 1，a = 1，b = 3/2，f(n) = 1。由于f(n)是一个常数，不涉及n的增长，所以时间复杂度为O(log_b(a)) = O(1)。

对于第三个时间函数T(n) = 3T(n/4) + nlogn，a = 3，b = 4，f(n) = nlogn。我们比较f(n)与n^log_b(a)的大小，即nlogn和4^log_4(3)的大小。因为对于任意正实数a，a^log_a(b) = b，所以4^log_4(3) = 3，可以看出f(n) = nlogn的增长速度大于3，所以时间复杂度为O(n^log_b(a)) = O(nlogn)。

综上所述，根据主定理，第一个时间函数的复杂度为O(n^2)，第二个时间函数的复杂度为O(1)，第三个时间函数的复杂度为O(nlogn)。

### 回答3：
利用主定理说明以下时间函数的复杂度：

1. T(n) = 9T(n/3) + n

根据主定理，我们可以将该递归式表示为：T(n) = aT(n/b) + f(n)，其中a = 9，b = 3，f(n) = n。

比较log_b(a)和c的大小，其中c = log_3(9) ≈ 2.08。由于c > log_b(a)，所以复杂度为O(n^c)。

因此，T(n)的复杂度为O(n^2.08)。

2. T(n) = T(2n/3) + 1

根据主定理，我们可以将该递归式表示为：T(n) = T(n/b) + f(n)，其中b = 3/2，f(n) = 1。

因为f(n)是常数，所以复杂度为O(log n)。

因此，T(n)的复杂度为O(log n)。

3. T(n) = 3T(n/4) + nlogn

根据主定理，我们可以将该递归式表示为：T(n) = aT(n/b) + f(n)，其中a = 3，b = 4，f(n) = nlogn。

比较log_b(a)和c的大小，其中c = log_4(3) ≈ 0.79。由于c < log_b(a)，所以复杂度为O(n^log_b(a))。

因此，T(n)的复杂度为O(n^log_4(3))。