00个人总结

最近,把极客时间上的算法看完之后,基本也就停留在看完的阶段了。今天的主要任务是把这部分东西,再总结再看一遍。尤其是排序算法,然后把一些结论性的东西总结一下,方便之后复习。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势。

数据结构

数组

数组用一块连续的内存空间,来存储相同类型的一组数据,最大的特点就是支持随机访问,但插入、删除操作也因此变得比较低效,平均情况时间复杂度为 O(n)。

链表

和数组相比,链表更适合插入、删除操作频繁的场景,查询的时间复杂度较高。

应用:LRU 缓存淘汰算法。

栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现(顺序栈),也可以通过链表来实现(链式栈)。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。可以利用动态扩容的数组实现支持动态扩容的顺序栈。

应用:浏览器前进和后退功能;函数调用;表达式求值,括号匹配。

队列

队列最大的特点就是先进先出,主要的两个操作是入队和出队。跟栈一样,它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列

在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,就需要像环一样的循环队列。基于数组实现的,受限于空间大小,不能像链表那样无限延伸。

对于循环队列,队列为空时,判断条件为 head==tail;当队列满时,(tail+1)%n=head,也就是说,tail 指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

不同于栈需要一个栈顶指针,因为涉及到出队和入队操作,所以队列需要两个指针:一个是 head 指针,指向队头;一个是 tail 指针,指向队尾(最后一个元素的下一个空白位置)。

阻塞队列就是入队、出队操作可以阻塞,并发队列就是队列的操作多线程安全。

------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道