【C# 数据结构与算法】 查找算法
2022/6/10 1:22:16
本文主要是介绍【C# 数据结构与算法】 查找算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
概览
查找算法相关的概念
查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。查找算法分类:
1)静态查找和动态查找;
注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2)无序查找和有序查找。
无序查找:被查找数列有序无序均可;
有序查找:被查找数列必须为有序数列。
平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
Pi:查找表中第i个数据元素的概率。
Ci:找到第i个数据元素时已经比较过的次数。
默认题目种出现概率是等概率
九大查找算法
查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 |
---|---|---|---|
顺序查找 | O(n) | O(1) | 无序或有序 |
二分查找(折半查找) | O(log2n) | O(1) | 有序 |
插值查找 | O(log2(log2n)) | O(1) | 有序 |
斐波那契查找 | O(log2n) | O(1) | 有序 |
哈希查找 | O(1) | O(n) | 无序或有序 |
二叉查找树(二叉搜索树查找) | O(log2n) | ||
红黑树 | O(log2n) | ||
2-3树 | O(log2n - log3n) | ||
B树/B+树 | O(log2n) |
这篇关于【C# 数据结构与算法】 查找算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2022-03-01沐雪多租宝商城源码从.NetCore3.1升级到.Net6的步骤
- 2024-05-08首个适配Visual Studio平台的国产智能编程助手CodeGeeX正式上线!C#程序员必备效率神器!
- 2024-03-30C#设计模式之十六迭代器模式(Iterator Pattern)【行为型】
- 2024-03-29c# datetime tryparse
- 2024-02-21list find index c#
- 2024-01-24convert toint32 c#
- 2024-01-24Advanced .Net Debugging 1:你必须知道的调试工具
- 2024-01-24.NET集成IdGenerator生成分布式全局唯一ID
- 2024-01-23用CI/CD工具Vela部署Elasticsearch + C# 如何使用
- 2024-01-23.NET开源的简单、快速、强大的前后端分离后台权限管理系统