相关疑难解决方法(0)

每当我考虑算法/数据结构时,我倾向于用常数替换log(N)部分.哦,我知道log(N)有所不同 - 但它在现实世界的应用程序中是否重要？

所有实际用途的log(无穷大)<100.

我真的很好奇现实世界的例子,这是不成立的.

澄清:

• 我理解O(f(N))
• 我对现实世界的例子感到好奇,其中渐近行为比实际表现的常数更重要.
• 如果log(N)可以用常量替换,它仍然可以用O(N log N)中的常量替换.

这个问题是为了(a)娱乐和(b)收集使用的论据,如果我(再次)进行关于设计性能的争议.

当然,我知道arraylist和linkedlist之间的性能差异.我自己运行了测试,看到了arraylist和linkedlist之间插入/删除和迭代的巨大差异,这是一个非常大的列表.

(纠正我,如果我错了)我们通常更喜欢arraylist over linkedlist,因为:

1)我们实际上比插入/删除更频繁地进行迭代.所以我们更喜欢迭代比插入/删除更快.

2)链表的内存开销远远超过了arraylist

3)没有办法在批量插入/删除时将列表定义为链表,在迭代时作为arraylist.这是因为arraylist和linkedlist具有根本不同的数据存储技术.

我错了第3点[我希望如此:)]？是否有可能将这两个数据结构的好处放在一个列表中？我想,数据结构设计师必须考虑到它.

我想我错过了一个非常明显的观点但是在我的Java教科书中找不到它.

我知道节点存储不一定必须在链接列表的内存中连续.这是否也意味着链表不可索引？如果是这样,那么在链表中找到项目的唯一方法就是遍历列表,右边,而你可以get通过索引从数组中查找？

Public Class IndexableLinkedList(Of T)
  Inherits LinkedList(Of T)

 '??? implement an index 'property' '

End Class