# 二、请编写python证明当 T(n) = 2T(n/2)+n, T(1) = 0 时, T(n) = nlog2(n), 假设 n 是 2 的指数倍
时间: 2023-06-19 14:04:01 浏览: 63
我们可以使用归纳法来证明这个结论。
首先,当 n=1 时,根据题目条件,T(1)=0,而 nlog2(n) = 1*log2(1) = 0,因此结论成立。
接着,假设当 n=k 时,T(k) = klog2(k) 成立,即:
T(k) = 2T(k/2) + k = 2*(k/2*log2(k/2)) + k = k*log2(k) - k + k = k*log2(k)
现在我们来证明当 n=2k 时,T(2k) = 2k*log2(2k)。
当 n=2k 时,有:
T(2k) = 2T(k) + 2k = 2k*log2(k) + 2k
因为 k 是 2 的指数倍,所以 log2(k) 是整数,因此我们可以将 2k*log2(k) 表示为 k*log2(k) + k*log2(2) = k*log2(k) + k。
于是,我们有:
T(2k) = 2k*log2(k) + 2k = k*log2(k) + k + k*log2(2) = k*log2(2k)
因此,当 n=2k 时,T(n) = nlog2(n) 成立。
综上所述,结论成立。
相关问题
编写python程序计算S n =1+1/2+1/3+…
可以使用以下代码来计算S n :
```python
n = int(input("请输入n的值:"))
sum = 0
for i in range(1, n + 1):
sum += 1 / i
print("S n 的值为:", sum)
```
运行程序后,输入 n 的值,程序会根据公式计算出 S n 的值并输出结果。
python编写程序计算sn=1+1/2+1/3....+1/n
以下是两种Python编写程序计算sn=1+1/2+1/3....+1/n的方法:
方法一:使用循环累加
```python
def calc_sn(n):
s = 0
for i in range(1, n+1):
s += 1/i
return s
if __name__ == '__main__':
n = int(input("请输入n的值:"))
sn = calc_sn(n)
print("sn的值为:", sn)
```
方法二:使用递归
```python
def calc_sn(n):
if n == 1:
return 1
else:
return 1/n + calc_sn(n-1)
if __name__ == '__main__':
n = int(input("请输入n的值:"))
sn = calc_sn(n)
print("sn的值为:", sn)
```