数据结构~时间复杂度-阿里云开发者社区

开发者社区> 云计算> 正文

数据结构~时间复杂度

简介:

常用数据结构的时间复杂度

程序的复杂度分为时间复杂度和空间复杂度,通过字面上可以看出它们的含义,下面我们主要来看一个集合的时间复杂度,这些集合基本包含了.net里的所有了,呵呵!

Data Structure Add Find Delete GetByIndex
Array (T[])

O(n)

O(n)

O(n)

O(1)

Linked list (LinkedList<T>)

O(1)

O(n)

O(n)

O(n)

Resizable array list (List<T>)

O(1)

O(n)

O(n)

O(1)

Stack (Stack<T>)

O(1)

-

O(1)

-

Queue (Queue<T>)

O(1)

-

O(1)

-

Hash table (Dictionary<K,T>)

O(1)

O(1)

O(1)

-

Tree-based dictionary

(SortedDictionary<K,T>)

 O(log n) 

 O(log n) 

 O(log n) 

-

Hash table based set (HashSet<T>)

O(1)

O(1)

O(1)

-

Tree based set (SortedSet<T>)

O(log n)

O(log n)

O(log n)

-

如何选择数据结构

Array (T[])

  • 当元素的数量是固定的,并且需要使用下标时。

Linked list (LinkedList<T>)

  • 当元素需要能够在列表的两端添加时。否则使用 List<T>。

Resizable array list (List<T>)

  • 当元素的数量不是固定的,并且需要使用下标时。

Stack (Stack<T>)

  • 当需要实现 LIFO(Last In First Out)时。

Queue (Queue<T>)

  • 当需要实现 FIFO(First In First Out)时。

Hash table (Dictionary<K,T>)

  • 当需要使用键值对(Key-Value)来快速添加和查找,并且元素没有特定的顺序时。

Tree-based dictionary (SortedDictionary<K,T>)

  • 当需要使用键值对(Key-Value)来快速添加和查找,并且元素根据 Key 来排序时。

Hash table based set (HashSet<T>)

  • 当需要保存一组唯一的值,并且元素没有特定顺序时。

Tree based set (SortedSet<T>)

  • 当需要保存一组唯一的值,并且元素需要排序时。

鸣谢

本文原文由Dennis Gao 发表自博客园,本人只是收藏之

本文章来自:http://www.cnblogs.com/gaochundong/p/3813252.html

相关参考资料:

本文转自博客园张占岭(仓储大叔)的博客,原文链接:数据结构~时间复杂度,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章