证明对正整数n≥3，算法BS的元素比较次数T(n) ≤5n/3-2。
证明对正整数n≥3，算法BS的元素比较次数T(n) ≤5n/3-2。
发布时间：2025-08-31 22:23:10
请在 下方输入 要搜索的题目：
推荐参考答案 (
由 快搜搜题库 官方老师解答 )
答案：本题的数学归纳法证明思路 l证明 n=3,4,5 时成立 l假设 n <=k 时都成立，证明 n= k+1时也成立。ln=3 时， T(3)=T(1)+T(2)+2=3 <= 5*3/3-2，命题成立。 ln=4 时， T(4)=T(2)+T(2)+2=4 <= 5*4/3-2，命题成立。 ln=5 时， T(4)=T(2)+T(3)+2=6 <= 5*5/3-2，命题成立。假设n<=k时命题成立。 n=k+1时, T(k+1)=T(ë(k+1)/2û)+T( é(k+1)/2ù)+2, ...(1) 当k≥6时，有k+1 > ë(k+1)/2û ≥ 3，k+1 > é(k+1)/2ù ≥ 3 所以有T(ë(k+1)/2û)≤5*(ë(k+1)/2û)/3-2, T(é(k+1)/2ù)≤5*(é(k+1)/2ù)/3-2 成立, ...(2) 又知 k+1= ë(k+1)/2û + é(k+1)/2ù , …(3)由(1-3)，命题得证。
相关试题
- 1.证明对正整数n≥3，算法BS的元素比较次数T(n) ≤5n/3-2。
- 2.已知T n ． （3）证明：对?n∈N ，有1≤T n ＜4．
- 3.已知f（x）=T n ，证明：对?n∈N 有1≤T n ＜4．
- 4.设m, n为整数,证明m n, m-n与mn中一定有一个是3的倍数。
- 5.判断一个数在n个整数的有序数组中出现的次数是否超过n/2次，所需的最小比较次数为（ ）。
- 6.设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是 。
- 7.N是正整数，N是否为一个整数的平方？（1）4N是一个整数的平方；（2）N^3是一个整数的平方；
- 8.t*=n t=t*n t=n t+=n
- 9.证明:对于任意正整数n,n^3 - n^2 n - 1不能被4整除。
- 10.要判断一个整数N（>10）是否素数，我们需要检查3到N之间是否存在奇数可以整除N。则这个算法的时间复杂度是：
