喀什师范学院学报
喀什師範學院學報
객십사범학원학보
JOURNAL OF KASHGAR TEACHERS COLLEGE
2009年
3期
1-3
,共3页
复杂度%特征标%离散的傅立叶变换DFT
複雜度%特徵標%離散的傅立葉變換DFT
복잡도%특정표%리산적부립협변환DFT
令G一个阶为n的有限群,复数域上的群代数同构于准对角矩阵代数.每一个这种同构叫作复数域上一个离散的傅立叶变换DFT,它是由两两不同构的不可约表示组成.计算一个群的常表示是一个相当困难的问题,1994年Baum和Clausen给出了计算超可解群DFT的算法,它的复杂度为O(|G||log||G|),2003年Clausen和Muller给出了可解群的一个算法,它的复杂度为O(p|G|2log|G|).主要对有限交换群来进行讨论,首先给出计算交换群的不可约表示的算法,并对算法进行分析,接下来计算这个算法的复杂度,计算的结果为O(|G|).
令G一箇階為n的有限群,複數域上的群代數同構于準對角矩陣代數.每一箇這種同構叫作複數域上一箇離散的傅立葉變換DFT,它是由兩兩不同構的不可約錶示組成.計算一箇群的常錶示是一箇相噹睏難的問題,1994年Baum和Clausen給齣瞭計算超可解群DFT的算法,它的複雜度為O(|G||log||G|),2003年Clausen和Muller給齣瞭可解群的一箇算法,它的複雜度為O(p|G|2log|G|).主要對有限交換群來進行討論,首先給齣計算交換群的不可約錶示的算法,併對算法進行分析,接下來計算這箇算法的複雜度,計算的結果為O(|G|).
령G일개계위n적유한군,복수역상적군대수동구우준대각구진대수.매일개저충동구규작복수역상일개리산적부립협변환DFT,타시유량량불동구적불가약표시조성.계산일개군적상표시시일개상당곤난적문제,1994년Baum화Clausen급출료계산초가해군DFT적산법,타적복잡도위O(|G||log||G|),2003년Clausen화Muller급출료가해군적일개산법,타적복잡도위O(p|G|2log|G|).주요대유한교환군래진행토론,수선급출계산교환군적불가약표시적산법,병대산법진행분석,접하래계산저개산법적복잡도,계산적결과위O(|G|).
