# 两种查找算法的比较

2019/04/12 12:53

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

List<PtCameraInfo> cameraList = new List<PtCameraInfo>();
List<string> cameraIdList = dataIds.Split(',').ToList();
List<PtCameraInfo> 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))
{
break;
}
}
}
View Code

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

List<PtCameraInfo> cameraList = new List<PtCameraInfo>();
List<string> cameraIdList = dataIds.Split(',').ToList();
List<PtCameraInfo> oldList = this.cameraList.Cameras.ToList();

//排序
this._cameraList.Sort(new Comparison<PtCameraInfo>((a, b) =>
{
}));
cameraIdList.Sort((a, b) =>
{
});

//高效查找
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))
{
k = j;
break;
}
}
}
View Code

3、使用Dictionary实现高效查找

0
0 收藏

0 评论
0 收藏
0