关键词: 二阶数乘, 算法复杂度, 最优算法

Abstract: In this paper,  we present a new and interesting combination optimization problem called two-order multiple problem. The problem is stated as follows. There are $n\geq 2$ integers $a_1$, $a_2$, $\cdots$, $a_n$, let $\pi$ be a permutation of $\{1,2,\cdots,n\}$ which also shows a solution to the problem. We must try to find the optimal permutation $\pi$ so that the value of $\sum^n_{i=1}a_{\pi_{i}}a_{\pi_{i+1}}$ is minimal, where $\pi_{n+1}=\pi_1$. We provide a polynomial-time algorithm with the complexity of $O(n\log{n})$ for it.

Key words: two-order multiple, algorithm complexity, optimal algorithm