java algorithms collections
1.0.0
自定义收集初级Java开发人员角色的技术访谈数据。
在此处查看整个列表
n时间复杂性 - 输入中的元素数量。
n在空间复杂性中 - 以表示输入所需的位单位的输入大小。
| 类型 | 姓名 | 解释 | 地位 | 例子 |
|---|---|---|---|---|
O(1) | 恒定时间 | 无论输入的大小如何 | 出色的 | 按键在哈希表中搜索 |
O(log n) | 对数时间 | 与输入数据的大小增加相比，执行时间的增加非常缓慢 | 出色的 | 二进制搜索（平均） |
O(n) | 线性时间 | 执行时间与输入数据的大小线性成正比 | 好的 | 蛮力搜索 |
O(n + k) | 组合/添加时间 | 两个单独输入的复杂性 | 好的 | 计数排序 |
O(n log n) | 准线性时间 | 随着输入尺寸的增加，由于对数增长，解决问题所需的分裂数量会缓慢增加 | 坏的 | 合并排序，堆排序 |
O(n^2) | 二次时间 | 涉及每个元素的嵌套迭代或比较 | 可怕 | 选择排序 |
O(2^n) | 指数时间 | 涉及对输入的所有可能组合的详尽搜索或枚举，执行时间指数增加 | 可怕 | TSP（动态编程） |
O(n!) | 阶乘时间 | 涉及对输入的所有可能组合的详尽搜索或枚举，执行时间会增加因素增加 | 可怕 | TSP（蛮力） |
| 类型 | 姓名 | 解释 | 地位 | 例子 |
|---|---|---|---|---|
O(1) | 恒定空间 | 无论输入大小如何 | 出色的 | 堆排序 |
O(log n) | 对数空间 | 与输入数据大小的增加相比，空间使用量增加了缓慢 | 出色的 | 快速排序 |
O(n) | 线性空间 | 空间用法与输入大小线性缩放 | 好的 | 合并排序 |
O(n + k) | 组合/添加空间 | 空间用法用n和k的总和线性缩放 | 坏的 | radix排序 |
| 学期 | 定义 | 例子 |
|---|---|---|
| 抽象数据类型（ADT） | 代表数据类型的高级描述，重点是其行为和操作，而不是特定的实现详细信息 | 堆栈，队列，字典，序列，集合 |
| 数据结构 | 实施特定数据类型，以特定方式组织和存储数据的技术或策略，以促进有效的操作 | 数组，链接列表，哈希表，树（二进制搜索树，堆，红色/黑树 |
| 类型 | 重复元素 | 元素的顺序 | 必须以特定顺序添加/删除 |
|---|---|---|---|
| 列表 | 允许 | 由索引 | 不 |
| 地图 | 允许值 | Java使用密钥的hashCode（）确定顺序，对我们而言，它没有排序 | 不 |
| 队列 | 允许 | 以定义的顺序检索 | 是的 |
| 放 | 禁止 | 仅在树上 | 是的 |
| 类型 | 界面 | 排序？ | 呼叫hashCode() ？ | 呼叫compareTo() ？ |
|---|---|---|---|---|
| arraylist | 列表 | 不 | 不 | 不 |
| LinkedList | 清单，Deque | 不 | 不 | 不 |
| Arraydeque | 队列，Deque | 不 | 不 | 不 |
| 哈希集 | 放 | 不 | 是的 | 不 |
| 树 | 设置，排序集 | 是的 | 不 | 是的 |
| linkedhashset | 放 | 不 | 是的 | 不 |
| 哈希图 | 地图 | 不 | 是的 | 不 |
| LinkedHashMap | 地图 | 不 | 是的 | 不 |
| Treemap | 地图，排序图 | 是的 | 不 | 是的 |
涉及排序的数据结构不允许零值。
