代換法解遞歸式
代換法解遞歸式
證明T(n)=T(n/2)+1的解為O(lgn)
證明T(n)=T(n/2)+1的解為O(lgn)
數(shù)學人氣：750 ℃時間：2020-06-13 14:56:43
優(yōu)質解答
首先你需要知道在靠近計算機的領域lg的默認底數(shù)是2.另外你沒有給出Base Case,那么我假設它是θ(1).證明如下:Assume:T(k)≤c•lgn,k≤n,c is a constant.∴T(n)=T(n/2) 1≤c•lg(n/2) 1=c•lgn-(1-1)...
我來回答
類似推薦
- 代換解題法
- 如何解這個遞歸方程
- 1、 用一個鑄件可以做6個零件,6個鑄件的加工余料又可以做成一個鑄件,用36個鑄件,可加工出多少個零件?
- 2只紅球與4只黑球的重量相等,3只黑球的重量等于1只紅球加1只藍球,那么幾只藍球的重量等于3只紅球加4只黑球?
- 離散數(shù)學題：遞歸式轉為非遞歸式
- 若單項式5x4y和25xnym是同類項，則m+n的值為_．
- 已知函數(shù)f(x)=ax+b,若函數(shù)y=f(x)的圖像經(jīng)過點（1,3）,（4,9）,求f(3x+2)拜托了各位
- 已知R1=2歐姆，R3=5歐姆，R2=R4，電壓表讀數(shù)U1=2.4伏特，U2=4伏特，則電阻R2為（ ?。?A.4歐姆 B.6歐姆 C.8歐姆 D.10歐姆
- 作文：記某某某的一堂課
- Where are () (they )keys
- 你的姐姐在哪里工作?英語怎么說
- 的中心句是什么?
猜你喜歡
- 1不等式2cosx>1的解集
- 2照樣子寫詞語 氣喘吁吁 __
- 3小學語文詞語解釋第五課中的硬說如何解釋
- 4如果甲乙兩數(shù)的最大公因數(shù)為144,他們的最小公倍數(shù)是36,這兩個數(shù)是幾?
- 5測定某液態(tài)鹵代烴RX（R是烷烴基,X是某鹵素原子）相對分子質量的放法
- 6在括號里填上帶 美 的詞語 雄壯的美麗 叫 （ ） 清秀美麗叫（?。【旅篮玫拿溃ǎ ∪A貴美麗叫（）
- 7All students have to face their own problems when they are growing up.
- 8滑動摩擦力總是阻礙物體運動
- 9incident,accident,event,affair 和 business的用法區(qū)別?
- 10衛(wèi)星在離月球較遠的圓軌道上運行時,與月球距離為h1,離較近的距離為h2,月球半徑為r,求衛(wèi)星在距離h1,h2軌道上運行的動能之比
- 11有一次數(shù)學比賽,王平和小方做題比是3:2,王平比小方多做2題,王平和小方各做多少道題?
- 12If you are stressd out and angry you should eat more( )