博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
两种查找算法的比较
阅读量:5874 次
发布时间:2019-06-19

本文共 1772 字,大约阅读时间需要 5 分钟。

1、普通查找:双层循环遍历,第二层循环中找到即break,查找时间复杂度O(M*N/2)

List
cameraList = new List
();List
cameraIdList = dataIds.Split(',').ToList();List
oldList = this.cameraList.Cameras.ToList();for (int i = 0; i < cameraIdList.Count; i++){ string cameraId = cameraIdList[i]; for (int j = 0; j < _cameraList.Count; j++) { PtCameraInfo camera = _cameraList[j]; if (camera.ID == cameraId && !oldList.Exists(a => a.ID == camera.ID)) { cameraList.Add(camera); break; } }}
View Code

2、高效查找:排序虽然费时,但数量级低,所以耗时很低,排序时间复杂度O(M*logM+N*logN),查找过程也是双层循环,但第二层循环比较省时,查找时间复杂度O(M*logN),总的时间复杂度:O(M*logM+N*logN+M*logN)

List
cameraList = new List
();List
cameraIdList = dataIds.Split(',').ToList();List
oldList = this.cameraList.Cameras.ToList();//排序this._cameraList.Sort(new Comparison
((a, b) =>{ return string.Compare(a.ID.PadLeft(36, '0'), b.ID.PadLeft(36, '0'));}));cameraIdList.Sort((a, b) =>{ return string.Compare(a.PadLeft(36, '0'), b.PadLeft(36, '0'));});//高效查找int k = 0;for (int i = 0; i < cameraIdList.Count; i++){ string cameraId = cameraIdList[i]; for (int j = k; j < _cameraList.Count; j++) { PtCameraInfo camera = _cameraList[j]; if (camera.ID == cameraId && !oldList.Exists(a => a.ID == camera.ID)) { cameraList.Add(camera); k = j; break; } }}
View Code

说明:cameraList的数量级是2万,当cameraIdList数量从1到大约1000时,高效查找耗时始终是0.1秒多左右,而普通查找,当cameraIdList数量很少时,很快,0.05秒,当cameraIdList数量接近1000时,大约2秒。

转载于:https://www.cnblogs.com/s0611163/p/10694987.html

你可能感兴趣的文章
4.2. PHP crypt()
查看>>
commandLink/commandButton/ajax backing bean action/listener method not invoked (转)
查看>>
RedHat 5.6_x86_64 + ASM + RAW+ Oracle 10g RAC (二)
查看>>
就是一个表格
查看>>
找回使用Eclipse删除的文件
查看>>
移动开发Html 5前端性能优化指南
查看>>
《系统架构师》——操作系统和硬件基础
查看>>
如何看待一本图书
查看>>
Linux 中如何通过命令行访问 Dropbox
查看>>
开发进度——4
查看>>
JS里验证信息
查看>>
Akka actor tell, ask 函数的实现
查看>>
windows10 chrome 调试 ios safari 方法
查看>>
Netty 4.1.35.Final 发布,经典开源 Java 网络服务框架
查看>>
详解Microsoft.AspNetCore.CookiePolicy
查看>>
SCDPM2012 R2实战一:基于SQL 2008 R2集群的SCDPM2012 R2的安装
查看>>
SQL SERVER中字段类型与C#数据类型的对应关系
查看>>
Linux lsof命令详解
查看>>
SVG path
查看>>
js判断checkbox是否选中
查看>>