我用9个链表制作了一个游戏，另外1个链表获取了其他9个链表的所有地址。因此，类似于使用链表的二维数组。
我正在尝试计算我的数据结构适合且优于二维数组的 Big-O，但我担心三件事。
存在名为a[10][10]的二维数组，当我插入a[5][5]=1时，它是O(1)吗？
链表有N个节点，那么要找到最后一个节点是O(N)吗？
正如我之前所说，我创建了一个链接列表，看起来像 二维数组，每个链表有 N 个节点。 如果我找到每个链表的最终节点并将其移动到每个头。是O(N^2)吗？
最佳答案
2 dimensional array called a[10][10] exists, when I insert a[5][5]=1 is it O(1)?
不，它是O(行索引+列索引)，因为你需要通过遍历找到一个链表，然后通过另一次遍历找到其中的节点。
A linked list exists with N nodes, then in order to find the final node is it O(N)?
这取决于实现。有些有一个特殊的链接到最终节点，然后它是O(1)。单链表确实是O(n)。
As I said before, I've made a linked list which looks like a 2 dimensional array and each linked list has N nodes. If i find each linked list's final node and moves it to each head. Is it O(N^2)?
这取决于上一点:O(n) 或 O(n^2)。
关于c++ - Big-O 用于二维数组和链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30703954/