MIT算法導(dǎo)論三 分治法

分治法分為三個(gè)步驟:
Divide - 將一個(gè)問題拆分成若干個(gè)子問題(規(guī)模更小)
Conquer - 通過遞歸的方法分別解決第一步中的每個(gè)子問題
Combine - 將各個(gè)子問題的結(jié)果合并起來(lái)得到整個(gè)問題的結(jié)果

典型的分治法算法

  • 歸并排序(Merge sort之前介紹過)
    T(n) = 2T(n/2) + n | 滿足主定理Case2
    =》T(n) = Θ(nlgn)

  • 二分查找(Binary search)
    在一個(gè)已經(jīng)排序的數(shù)組中找到x
    把x于數(shù)組的中間節(jié)點(diǎn)比較,有三種結(jié)果:
    1.x=middle,返回結(jié)果
    2.x<middle,左半邊數(shù)組進(jìn)行遞歸查找
    3.x>middle窝爪,同理右半邊數(shù)組進(jìn)行遞歸查找
    T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)

  • 乘方問題(Power the number
    給定x,n>0,求解xn
    if n是偶數(shù)衙伶,xn = xn/2 * xn/2
    if n是基數(shù),xn = x(n-1)/2 * x(n-1)/2 * x
    T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)

  • 斐波那契數(shù)列
    0 1 1 2 3 5 8 13 ...

    樸素算法:Fn = Fn-1 + Fn-2
    算法效率為Ω(φn)呼畸,指數(shù)級(jí)別的痕支,遞歸子問題的規(guī)模沒有明顯減小,并且又重復(fù)計(jì)算的部分

    自底向上算法:計(jì)算 0 1 1 2 3 5... 直到Fn
    避免了重復(fù)計(jì)算蛮原,算法效率提高到了Θ(n)

    遞歸平方算法:

    定理

    問題的求解即成為了矩陣的乘方問題卧须,算法效率于是提高到了Θ(lgn)

  • 矩陣乘法nxn階矩陣
    有兩個(gè)矩陣A[ij]、B[ij]儒陨,求解C=A*B
    Cij=Σ(Aik * Bkj) | k <- 1 to n
    樸素算法:需要三層循環(huán)(i\j\k分別從1到n循環(huán)計(jì)算花嘶,見文末補(bǔ)充),算法的效率為Θ(n3)

    分治算法:將矩陣分成四個(gè)相同大小

    分解矩陣

    r=ae+gb
    s=af+bh
    t=ce+dg
    u=cf+dh
    T(n) = 8T(n/2) + Θ(n2) | 分成遞歸八個(gè)乘法蹦漠,每個(gè)小問題是原來(lái)的1/2椭员,加上4次矩陣加法運(yùn)算
    => T(n) = Θ(n3) 效率并沒有提高

    Strassen算法:
    主定理方法可知必須想辦法將2中遞歸式中的系數(shù)8減少。Strassen提出了一種將系數(shù)減少到7(log27<3)的分治法方案
    P1=a(f-h)
    P2=(a+b)h
    P3=(c+d)e
    P4=d(g-e)
    P5=(a+d)(e+h)
    P6=(b-d)(g+h)
    P7=(a-c)(e+f)
    r=P5+P4-P2+P6
    s=P1+P2
    t=P3+P4
    u=P5+P1-P3-P7
    問題轉(zhuǎn)變成遞歸7次乘法和18次加減法
    T(n) = 7T(n/2) + Θ(n2) =》 T(n) = Θ(nlg7) = Θ(n2.81)
    效率提高笛园,并且因?yàn)槭侵笖?shù)級(jí)增長(zhǎng)隘击,當(dāng)n更大時(shí)提升效率明顯
    ~現(xiàn)在理論上矩陣乘法的效率最好的是:Θ(n^2.376…)侍芝。但是在這眾多的優(yōu)化算法中,Strassen算法卻是最簡(jiǎn)單的~


補(bǔ)充:矩陣乘法nxn階矩陣樸素算法
for i ← 1 to n 
   do for j ← 1 to n 
       do c[i][j] ← 0 
           for k ← 1 to n 
               do c[i][j] ← c[i][j] + a[i][k]? b[k][j] 
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末埋同,一起剝皮案震驚了整個(gè)濱河市州叠,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌凶赁,老刑警劉巖咧栗,帶你破解...
    沈念sama閱讀 206,214評(píng)論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異虱肄,居然都是意外死亡致板,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,307評(píng)論 2 382
  • 文/潘曉璐 我一進(jìn)店門咏窿,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)斟或,“玉大人,你說(shuō)我怎么就攤上這事翰灾÷拼猓” “怎么了?”我有些...
    開封第一講書人閱讀 152,543評(píng)論 0 341
  • 文/不壞的土叔 我叫張陵纸淮,是天一觀的道長(zhǎng)平斩。 經(jīng)常有香客問我,道長(zhǎng)咽块,這世上最難降的妖魔是什么绘面? 我笑而不...
    開封第一講書人閱讀 55,221評(píng)論 1 279
  • 正文 為了忘掉前任,我火速辦了婚禮侈沪,結(jié)果婚禮上揭璃,老公的妹妹穿的比我還像新娘。我一直安慰自己亭罪,他們只是感情好瘦馍,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,224評(píng)論 5 371
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著应役,像睡著了一般情组。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上箩祥,一...
    開封第一講書人閱讀 49,007評(píng)論 1 284
  • 那天院崇,我揣著相機(jī)與錄音,去河邊找鬼袍祖。 笑死底瓣,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的蕉陋。 我是一名探鬼主播捐凭,決...
    沈念sama閱讀 38,313評(píng)論 3 399
  • 文/蒼蘭香墨 我猛地睜開眼拨扶,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了茁肠?” 一聲冷哼從身側(cè)響起屈雄,我...
    開封第一講書人閱讀 36,956評(píng)論 0 259
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎官套,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蚁孔,經(jīng)...
    沈念sama閱讀 43,441評(píng)論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡奶赔,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,925評(píng)論 2 323
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了杠氢。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片站刑。...
    茶點(diǎn)故事閱讀 38,018評(píng)論 1 333
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖鼻百,靈堂內(nèi)的尸體忽然破棺而出绞旅,到底是詐尸還是另有隱情,我是刑警寧澤温艇,帶...
    沈念sama閱讀 33,685評(píng)論 4 322
  • 正文 年R本政府宣布因悲,位于F島的核電站,受9級(jí)特大地震影響勺爱,放射性物質(zhì)發(fā)生泄漏晃琳。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,234評(píng)論 3 307
  • 文/蒙蒙 一琐鲁、第九天 我趴在偏房一處隱蔽的房頂上張望卫旱。 院中可真熱鬧,春花似錦围段、人聲如沸顾翼。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,240評(píng)論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)适贸。三九已至,卻和暖如春段磨,著一層夾襖步出監(jiān)牢的瞬間取逾,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,464評(píng)論 1 261
  • 我被黑心中介騙來(lái)泰國(guó)打工苹支, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留砾隅,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 45,467評(píng)論 2 352
  • 正文 我出身青樓债蜜,卻偏偏與公主長(zhǎng)得像晴埂,于是被迫代替她去往敵國(guó)和親究反。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,762評(píng)論 2 345

推薦閱讀更多精彩內(nèi)容