第八周·总结·数据结构预算法

用户头像
刘璐
关注
发布于: 2020 年 07 月 29 日
第八周·总结·数据结构预算法

一、时间复杂度与空间复杂度

1.时间复杂度:算法执行语句的次数

(1) O(2^n)表示对n数据处理需要进行2^n次计算

(2) O(1)、O(log(n))、O(n a)多项式时间复杂度

(3) O(a n)、O(n!)非多项式时间复杂度

2.空间复杂度

(1) 一个算法在运行过程中临时占用存储空间大小的亮度

(2) O(n)表示需要临时存储N个数据



二、NP问题

P:能在多项式时间复杂度内解决的问题

NP:能在多项式时间复杂度内验证答案正确与否的问题

NP-hard: 比NP问题更难得问题

NP完全问题:是一个NP-hard问题,也是一个NP问题



三、数组

创建数组必须要内存中一块儿连续的空间。且必须存放相同的数据类型。随机快速读写是数组的一个重要特性,使用数组的下表访问数据,时间复杂度是O(1)



四、链表

1.链表可以使用零散的内存空间存储数据。要想在链表中查找一个数据,只能遍历链表,所以链表的查找复杂度总是O(N)

2.链表中增删数据要比数组性能好得多。

3.数组链表结合,可以实现快速查找和快速增删。



五、Hash表

1.使用value的hashcode求余的方式,实现快速定位。

2.当余数出现冲突时,使用hash链表解决。



六、栈

1.数组和链表都被成为线性表

2.栈就是在线性表的基础上加了限制条件:后进先出

3.栈帧:JVM 执行 Java 程序时需要装载各种数据到内存中,不同的数据存放在不同的内存区中(逻辑上),这些数据内存区称作运行时数据区(Run-Time Data Areas)。其中 JVM Stack(Stack 或虚拟机栈、线程栈、栈)中存放的就是 Stack Frame(Frame 或栈帧、方法栈)。



七、队列

队列也是一种操作首先的线性表,栈是后劲先出,而队列是先进先出。

典型场景:应用生产者消费者。



八、二叉排序树

1.左子树上所有节点的值均小于或等于它的根节点的值。

2.右紫薯上所有节点的值均大于或等于它的根节点的值。

3.左右紫薯也分别为二叉排序树。



九、二叉不平衡数



十、平衡二叉(排序)树



用户头像

刘璐

关注

还未添加个人签名 2018.03.29 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”,便于分类
2020 年 07 月 29 日 17:45
回复
没有更多了
第八周·总结·数据结构预算法