※ 引述《Arton0306 (烏索普阿阿阿~~~)》之銘言： : 在計算生物學中 : 很多NPC NPHard的問題 : 像給一蛋白質序列和各鍵結之間的能量大小等 : 要計算出其3D立體結構 使其具最小自由能 : 像這個就是NPHard : 另外物理系的他們也有研究用simulation的方法 : 把分子、原子等的物理之間的關系輸入進去 : 用電腦去模擬 : 關於模擬的方式其時間複雜度是怎麼算呢？ : 若把蛋白質看成一粒粒粒子 : 或是看成一單位一單位的胺基酸 : 那麼把各胺基酸之間的作用關系等輸入 : 每當新增一個胺基酸時 : 也只是多算這個胺基酸和原有胺基酸的作用關系 ^^^^^^^^^^^^^^^^^^^^^^^^ 這種計算方式叫做greedy algorithm， 通常只有一些簡單的問題才能夠用greedy的方式來看待。 : 感覺起來似乎是O(n^2) : 但這樣就和NPHard有衝突了 假設原來的胺基酸是 LRVK，新增一個胺基酸 G 由於蛋白質是三維結構，跟這個新的G的互動方式不會只是(LRVK,G)這樣的線性關係。 也還需要考慮 (L,G),(R,G),(V,G),(K,G),... ,(LRV,G), (RVK,G),...等互動。 任何模擬系統都差不多是這樣，新加入一個東西時， 要考慮的是這個東西和原先"所有"東西的互動，所以用暴力法來看的話， 計算複雜度至少是是 2^n，而不是2^n。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.230.222.123