https://scholars.lib.ntu.edu.tw/handle/123456789/117278
標題: | 最大總和區間相關變型題的快速演算法 Efficient Algorithms for Some Variants of the Maximum-Sum Segment Problem |
作者: | 鄭智懷 Cheng, Chih-Huai |
關鍵字: | 最大總和區間;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://ntur.lib.ntu.edu.tw//handle/246246/54107 | 其他識別: | en-US |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。