Skip to content

091-week1 #47

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
DevinSu opened this issue Apr 18, 2019 · 0 comments
Open

091-week1 #47

DevinSu opened this issue Apr 18, 2019 · 0 comments

Comments

@DevinSu
Copy link
Contributor

DevinSu commented Apr 18, 2019

本周主要是通过专栏以及周末上的课程对基本的数据结构数组 链表,队列,栈以及简单的搜索排序等进行复习
着重复习了时间复杂度和空间复杂度分析
对最好,最坏,平均,均摊时间复杂度进行梳理
以及算法稳定性

学习总结:
链表:
针对删除链表元素时候,不能简单认为其是O(1),而是要看删除方法传入的参数是什么,如果是待删除的节点则我们是需要遍历找到他的前置节点,才能删除这个时候是O(N)

数组部分:
数组是连续内存空间,查询效率高,增删改效率低。
一般数组算法都要遍历数组
如果数组有顺序则一般采用二分
如果没顺序一般用hash
一般外层的循环省不掉,考虑内层遍历优化

栈部分:
栈属于特殊的线性结构,先进后出。
一般用于对顺序有要求的场景
递归部分:
递归一般可以都可以用栈转换
递归的时间复杂度分析方法:递归树,然后推出递推公式。
找到退出条件。
两种递归方式:自顶向下或者自底向上分析

排序部分:
基础排序算法思想,快排的思想,归并的思想,以及桶排序的思想。思想很重要,可以应用到别的算法上

当海量数据时候散列表会占用很大内存,这个时候不如顺序扫描
原地排序:原地排序不是空间复杂度为O(1)的算法,不一定,知识不需要额外空间,在原数组上进行排序

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant