我正在努力掌握大O符号。它看起来很抽象。我选择了最常见的数据结构--数组、哈希表、链表(单链表和双链表)和二叉树,并猜测了最常见的操作--插入和搜索--的大O符号。这是一个惯性视图的准备工作。我只需要学习基础知识,而不是阅读一整本关于算法的教科书,尽管这将是理想的。下表是否有效?
Data Structure Big O Search Big O Insert
Array O(1) O(n)
Hash O(1) O(1)
Single Linked List
我为一个链表dvd清单程序编写了代码,该程序允许我使用for循环遍历列表,并将列表中的每个dvd标题与用户输入的dvd标题进行比较。如果书名匹配,它将打印出该书目的库存份数。代码如下:
movieToCommand = input.substring(2, input.length()).toLowerCase();
for (int i = 1; i <= movies.length(); i++) {
if (movies.get(i).getTitle().equals(inputMovie)) {
System.out.println("There are
我有下面的链表结构:
struct Node {
int type;
int otherInfo;
Node * next;
}
我想创建一个排序的(最终)链表,跟踪每个"type“出现的次数。示例节点为:
struct Node2 {
int type;
int frequency;
//A linked list to keep track of the "otherInfo"
Node2 * next;
}
我目前的算法是O(n^2),这是不合理的,因为原始链表有时可以有超过30,000个元素。有没有更有效的
链表
对于实际操作,链表的插入时间复杂度为O(1),但需要O(n)时间遍历到正确的位置。大多数在线资源将链接列表的平均插入时间列为O(1):
https://stackoverflow.com/a/17410009/10426919
https://www.bigocheatsheet.com/
https://www.geeksforgeeks.org/time-complexities-of-different-data-structures/
BST
二进制搜索树的插入需要遍历节点,所需时间为O(log )。
问题
Am I mistaken to believe that insert
双向链表实现了链表的惯用遍历,我想为什么二叉树不行呢?传统上,二叉树或树通常是单向的,这意味着,给定具有足够数量的节点的大树,查找叶节点的运行时间可能会很昂贵。
如果在找到这样一个节点后,为了找到下一个节点,我可以向后遍历树的根,与另一次深度优先搜索树的每个节点相比,这不是更有优势吗?我以前从未考虑过这一点,直到认识到双向链表和二叉树的结合可能会带来潜在的好处。
例如,如果我使用一个内部类
class Tree<T> {
private class TwoWayNode {
var data : T
var lef