图论分割算法算子消耗模型OCM的建立与分析

• 作者: 刘佳 吕彩霞 李哲英 李荪
• 来源期刊: 电子测量与仪器学报
• 学科: 工学
• 关键词: 图论分割 计算复杂度 算子消耗模型
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 学术论文
• 页码范围: 1011-1018
• 页数: 8页
• 分类号: TN301.5
• 字数: 6724字
• 语种: 中文
• DOI: 10.3724/SP.J.1187.2012.01011

摘要

算法时间复杂度与算法的具体实现方法有关,为使时间复杂度分析具有普遍性,提出了微处理器系统无关的算法操作算子消耗模型(OCM).根据对最小生成树(MST)图论分割算法的分析,提取算法中操作算子消耗特性,建立了该算法的OCM.MST图论分析算法的OCM给出了该算法的固有计算复杂度,在选择了微处理器系统后,可通过OCM直接获得该算法的时间复杂度.分析结果表明,对于特定尺寸的图像,降低MST图论分割算法时间复杂度的关键是减少加法、除法和比较算子的操作,或优化这3个操作算子的执行过程.同时,对于具有加、减、乘、除、开方和比较运算的微处理系统,该算法算子总消耗量随着k的增大会逐渐减小,当k值趋于无穷大时,算子总消耗量处于稳定的状态.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李哲英	北京联合大学北京市信息服务重点实验室	44	140	7.0	8.0
2	吕彩霞	北京联合大学北京市信息服务重点实验室	7	11	2.0	3.0
3	刘佳	北京联合大学北京市信息服务重点实验室	23	34	4.0	4.0
4	李荪	北京交通大学电子信息工程学院	1	4	1.0	1.0