求解证明题1：求解递推方程并证明结论 求 丁(n)=2T（n/2)+n/logn 的解，

### 回答1：
首先，我们可以将这个式子写成递归形式：

求解时间复杂度为 T(n) = 2T(n/2) + n/log(n) 的问题。

接下来，我们可以使用主定理来求解这个递归式的时间复杂度。

主定理的一般形式是：T(n) = aT(n/b) + f(n)，其中 a ≥ 1，b > 1，f(n) 是一个非负函数。

根据主定理，我们可以将 T(n) 的时间复杂度分为以下三种情况：

1. 如果 f(n) = O(n^c) 且 a < b^c，则 T(n) = Θ(n^c)。
2. 如果 f(n) = Θ(n^c log^k(n))，则 T(n) = Θ(n^c log^(k+1)(n))。
3. 如果 f(n) = Ω(n^c) 且 a > b^c，则 T(n) = Θ(f(n))。

根据上述情况，我们可以得到：

- a = 2，b = 2，f(n) = n/log(n)，因此，c = log2(2) = 1，k = 0。
- f(n) = Θ(n^c log^k(n))，其中 c = 1，k = 0。
- 因此，根据情况 2，T(n) = Θ(n log(n))。

因此，这个式子的时间复杂度为 Θ(n log(n))。

### 回答2：
首先解递推方程：

根据递推方程 丁(n) = 2T(n/2) / (n/logn)，我们可以将递推式进行展开：

丁(n) = 2T(n/2) / (n/logn)
= 2 * (2T(n/4) / ((n/2)/(log(n/2))))
= 2² * T(n/4) / ((n/2)/(log(n/2)))²
= 2³ * T(n/8) / ((n/4)/(log(n/4)))³
= ...
= 2^k * T(n/2^k) / ((n/2^k)/(log(n/2^k)))^k

其中，k = logn。

当 n/2^k = 1 时，即 n = 2^k，我们得到 k = logn，意味着到达基本情况。

当 n/2^k = 1，即 n = 2^k，将其代入上述公式，得到：
丁(n) = 2^k * T(1) / (1/(log(1)))^k
= 2^k * T(1) / (1/0)^k （0 的对数是无穷大）
= 2^k * T(1) / 0^k

因为 0 的 k 次方也是无穷大，所以这个递推方程没有明确的解。

综上所述，无法求解递推方程丁(n) = 2T(n/2) / (n/logn) 的解。

### 回答3：
要证明丁(n) = 2T(n/2) n/logn的解，首先需要解递推方程丁(n) = 2T(n/2)。

根据递推方程的定义，丁(n) 的值取决于 2T(n/2)。而T(n/2) 的值又取决于 2T(n/4)，以此类推。

假设对于一个特定的K，有丁(2^K) = 2T(2^(K-1))。将这个假设代入递推方程中，我们有：

丁(2^K) = 2T(2^(K-1)) = 2*(2T(2^(K-1)/2)) = 2*(2T(2^(K-2)))

继续代入递推方程中，我们可以得到：

丁(2^K) = 2*(2*(2T(2^(K-2)/2))) = 2*(2*(2T(2^(K-3))))

继续推导下去，我们可以得到：

丁(2^K) = 2*(2*(2*...*(2*T(1)))) = 2^K * T(1)

其中，有K个2相乘。

又因为丁(1) = T(1) = 1/log(1)，所以我们可以推断出：

丁(n) = 2^(logn) * T(1) = n * T(1) = n/logn

所以可以得出结论，丁(n) = 2T(n/2) n/logn 的解为 n/logn。