数据结构时间复杂度及如何选择数据结构.pdf

《数据结构时间复杂度及如何选择数据结构.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、常用数据结构的时间复杂度DataStructureAddFindDeleteGetByIndexArray(T[])O(n)O(n)O(n)O(1)Linkedlist(LinkedList)O(1)O(n)O(n)O(n)Resizablearraylist(List)O(1)O(n)O(n)O(1)Stack(Stack)O(1)–O(1)–Queue(Queue)O(1)–O(1)–Hashtable(Dictionary)O(1)O(1)O(1)–Tre

2、e-baseddictionary(SortedDictionary)O(logn)O(logn)O(logn)–Hashtablebasedset(HashSet)O(1)O(1)O(1)–Treebasedset(SortedSet)O(logn)O(logn)O(logn)–如何选择数据结构Array(T[])当元素的数量是固定的，并且需要使用下标时。Linkedlist(LinkedList)当元素需要能够在列表的两端添加时。否则使用List。Res

3、izablearraylist(List)当元素的数量不是固定的，并且需要使用下标时。Stack(Stack)当需要实现LIFO（LastInFirstOut）时。Queue(Queue)当需要实现FIFO（FirstInFirstOut）时。Hashtable(Dictionary)当需要使用键值对（Key-Value）来快速添加和查找，并且元素没有特定的顺序时。Tree-baseddictionary(SortedDictionary)当需要使

4、用价值对（Key-Value）来快速添加和查找，并且元素根据Key来排序时。Hashtablebasedset(HashSet)当需要保存一组唯一的值，并且元素没有特定顺序时。Treebasedset(SortedSet)当需要保存一组唯一的值，并且元素需要排序时。Array在计算机程序设计中，数组（Array）是最简单的而且应用最广泛的数据结构之一。在任何编程语言中，数组都有一些共性：数组中的内容是使用连续的内存（ContiguousMemory）来存储的。数组中的所有元素

5、必须是相同的类型，或者类型的衍生类型。因此数组又被认为是同质数据结构（HomegeneousDataStructures）。数组的元素可以直接被访问。比如你需要访问数组的第i个元素，则可以直接使用arrayName[i]来访问。对于数组的常规操作包括：分配空间（Allocation）数据访问（Accessing）在C#中，可以通过如下的方式声明数组变量。C#1intallocationSize=10;2bool[]booleanArray=newbool[allocationSize];3

6、FileInfo[]fileInfoArray=newFileInfo[allocationSize];上面的代码将在CLR托管堆中分配一块连续的内存空间，用以容纳数量为allocationSize，类型为arrayType的数组元素。如果arrayType为值类型，则将会有allocationSize个未封箱（unboxed）的arrayType值被创建。如果arrayType为引用类型，则将会有allocationSize个arrayType类型的引用被创建。如果我们为FileInfo[]数

7、组中的一些位置赋上值，则引用关系为下图所示。.NET中的数组都支持对元素的直接读写操作。语法如下：1//读数组元素2boolb=booleanArray[7];34//写数组元素5booleanArray[0]=false;访问一个数组元素的时间复杂度为O(1)，因此对数组的访问时间是恒定的。也就是说，与数组中包含的元素数量没有直接关系，访问一个元素的时间是相同的。ArrayList由于数组是固定长度的，并且数组中只能存储同一种类型或类型的衍生类型。这在使用中会受到一些限制。.NET提供了一种数

8、据结构ArrayList来解决这些问题。1ArrayListcountDown=newArrayList();2countDown.Add(3);3countDown.Add(2);4countDown.Add(1);5countDown.Add("blastoff!");6countDown.Add(newArrayList());ArrayList是长度可变的数组，并且它可以存储不同类型的元素。但这些灵活性是以牺牲性能为代价的。在上面Array的描述中，我们知道Array