請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34271
標題: | 最大總和區間相關變型題的快速演算法 Efficient Algorithms for Some Variants of the Maximum-Sum Segment Problem |
作者: | Chih-Huai Cheng 鄭智懷 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 最大總和區間, maximum-sum segment, |
出版年 : | 2006 |
學位: | 碩士 |
摘要: | 找尋最大總和區間是個既基礎且重要的數列分析問題。給定一個實數數列A,我們找區間A(i,j)使得該區間的總和為最大。這類問題在生物序列上有找重複區段、富含C,G的區域以及設計低時間複雜度的篩選器等應用。本篇碩士論文探討兩種最大總和區間的變型問題,並提出解決的快速演算法。
我們研究前k大總和區間問題並且提出時間複雜度為O(n+klogk)的演算法。當我們要求答案要按照總和由大到小排列,我們是第一個提出k < n情況下的最佳解。考慮前k大總和區間問題在d維以及每維長度為n的情形下,我們的演算法時間複雜度是O(n^{2d-1}+klogk)。此外,我們也提出最大總和區間符合平均值下限或上限的線性演算法。 |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34271 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 638.43 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。