| 典型"稳定婚姻问题"的简明矩阵算法实现 |
| |
| 引用本文： | 范华,秦茂玲,张新法. 典型"稳定婚姻问题"的简明矩阵算法实现[J]. 山东师范大学学报(自然科学版), 2007, 22(1): 29-32 |
| |
| 作者姓名： | 范华 秦茂玲 张新法 |
| |
| 作者单位： | 山东师范大学信息科学与工程学院,250014,济南;山东师范大学信息科学与工程学院,250014,济南;山东师范大学信息科学与工程学院,250014,济南 |
| |
| 基金项目： | 国家自然科学基金;山东省自然科学基金 |
| |
| 摘 要： | 对于典型“稳定婚姻问题”，借助矩阵（二维数组）给出了一种简明的实现方法．在本算法中，所采用的存储结构和实现方法灵活巧妙，通俗易懂，方便实现；而且用于存储所要处理数据的内存空间相对于其它一些算法节省了一半，空间复杂度为O（1）；由于存储结构的巧妙性，算法的时间复杂度在最好的情况下为线性时间N，在最坏的情况下为O（N^2）．
|
| 关 键 词： | 稳定婚姻问题 矩阵 二维数组 |
| 修稿时间： | 2006-09-11 |
BRIFF MATRIX ALGORITHM REALIZATION OF TYPICAL"STABLE MARRIAGE PROBLEM" |
| |
| Fan Hua,Qin Maoling,Zhang Xinfa. BRIFF MATRIX ALGORITHM REALIZATION OF TYPICAL"STABLE MARRIAGE PROBLEM"[J]. Journal of Shandong Normal University(Natural Science), 2007, 22(1): 29-32 |
| |
| Authors: | Fan Hua Qin Maoling Zhang Xinfa |
| |
| Affiliation: | School of Information Science and Engineering,Shandong Normal University,250014,Jinan, China |
| |
| Abstract: | Regarding the typical"the stable marriage problem",we give one brief realization method with the help of the matrix(two-dimensional array).In this algorithm,the structure of memory and the realization method are nimble,ingenious,and easy to be understood,which facilitate the realization,and compared with other some ones,the memory used to store the data has been saved by half,and the complexity of the space is O(1).As a result of the ingenuity of memory structure,its complexity of the time can be linear time N in the best situation and that is O(N2)in the worst case. |
| |
| Keywords: | stable marriage problem matrix two-dimensional array |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
