学习总结(训练营第 8 课)

用户头像
看山是山
关注
发布于: 2020 年 07 月 29 日

时间复杂度

表示算法执行语句的次数

多项式复杂度:O(1), O(n), O(n^a)

非多项式复杂度:O(a^n), O(n!)

空间复杂度

表示临时占用的存储空间大小

O(n)

NP 问题

非确定性多项式问题 Non-deterministic polynomial,指其解的正确性能够被存在一个多项式检查算法的问题

常见数据结构

线性表

数组 - 连续内存空间

链表 - 长于增删,短于查找

Hash 表

通常是数组和链表的结合体。

先进后出 - 线程调用栈

队列

先进先出 - 生产者消费者队列

二叉排序树

便于二叉查找

存在不平衡性

平衡二叉树

左右子树的深度差不超过 1 的二叉排序树

通过旋转来确保插入和删除平衡

插入时最多只需要 2 次旋转

删除时次数不确定,时间复杂度 O(logN)

红黑树

最多只需要 3 次旋转就可以重新恢复平衡,时间复杂度 O(1)

大量增删的情况下,红黑树 效率比 平衡二叉树更高

平衡性不如平衡二叉树,查找效率要差一些

跳表

通过 多层 排序来实现增删查找效率的提升

通过 空间 换 时间,需要额外的存储空间

常用算法

递归算法

注意一定要有退出条件

贪心算法

不一定是最优解

改进贪心算法 - 最快路径(迪杰斯特拉算法)

递进遍历所有邻居节点,记录所有到该节点的最短路径;直到最终节点

动态规划

通过减小目标值,拆解大问题为小问题,通过归并小问题的最优解,寻找大问题的最优解

遗传算法

TODO - 待研究

不一定是最优解

用户头像

看山是山

关注

还未添加个人签名 2018.11.16 加入

还未添加个人简介

评论

发布
暂无评论
学习总结(训练营第 8 课)