软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2008年
3期
500-510
,共11页
刘培强%朱大铭%谢青松%范辉%马绍汉
劉培彊%硃大銘%謝青鬆%範輝%馬紹漢
류배강%주대명%사청송%범휘%마소한
算法%复杂性%指纹向量聚类%基因表达谱%团划分
算法%複雜性%指紋嚮量聚類%基因錶達譜%糰劃分
산법%복잡성%지문향량취류%기인표체보%단화분
证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figucroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n-p+1)·2P),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.
證明丟失值位數不超過2的指紋嚮量聚類問題為NP-Hard,併給齣Figucroa等人指紋嚮量聚類啟髮式算法的改進算法.主要改進瞭算法的實現方法.以鏈錶存儲相容頂點集閤,併以逐位掃描指紋嚮量的方法產生相容點集鏈錶,可將產生相容點集的時間複雜性由O(m·n·2p)減小為O(m·(n-p+1)·2P),可使劃分一箇唯一極大糰或最大糰的時間複雜性由O(m·p·2p)減小為O(m·2p).實際測試顯示,改進算法的空間複雜性平均減少為原算法的49%以下,平均可用原算法20%的時間求解與原算法相同的實例.噹丟失值位數超過6時,改進算法幾乎總可用不超過原算法11%的時間計算與原算法相同的實例.
증명주실치위수불초과2적지문향량취류문제위NP-Hard,병급출Figucroa등인지문향량취류계발식산법적개진산법.주요개진료산법적실현방법.이련표존저상용정점집합,병이축위소묘지문향량적방법산생상용점집련표,가장산생상용점집적시간복잡성유O(m·n·2p)감소위O(m·(n-p+1)·2P),가사화분일개유일겁대단혹최대단적시간복잡성유O(m·p·2p)감소위O(m·2p).실제측시현시,개진산법적공간복잡성평균감소위원산법적49%이하,평균가용원산법20%적시간구해여원산법상동적실례.당주실치위수초과6시,개진산법궤호총가용불초과원산법11%적시간계산여원산법상동적실례.
