java - 我应该为高效的方法选择高时间复杂度数据结构还是高空间复杂度数据结构？

Question

我必须在 ArrayList 和 LinkedList 这两种数据结构之间进行选择。我有两个操作 op_one，op_two。

如果我选择 ArrayList - 我最终会得到

for op_one ------ O(n), and at maximum n re-allocations
for op_two ------ O(1), and at maximum n re-allocations

如果我选择 LinkedList - 我最终会得到

for op_one ------ O(n), and zero re-allocations
for op_two ------ O(n), and zero re-allocations

我将存储数百万个可比较的元素。我将同样可能地进行这两项操作。我应该选择哪一个。

score 3 · Accepted Answer

我建议您将它们一起计时，并以一种现实的方式，看看哪个更快。如果它们没有显着不同，我会使用您认为最简单的方法。

虽然 ArrayList 和 LinkedLIst 的空间顺序相同，但 ArrayList 小得多。

除非您知道自己有性能问题，否则所有相同的清晰度通常是最重要的。

score 0 · Accepted Answer

(Question first understood as time complexity disregarding space. Request for clarifications made in comments)

I would use ArrayList (over LinkedList), not only because time complexity, but because it is simpler and it doesn't build a new node for each item.

Note overall complexity will be O(n) in either case: For ArrayList an O(n) + O(1), or prob*O(n) + (1-prob)*O(1) will be in the order of O(n).

Given equal complexity ( O(n) ), then you should find out actual execution time, or chose the easier to implement or maintain.

score 0 · Accepted Answer

考虑到在现代架构中，内存带宽通常是瓶颈。因此，有时计算结果比存储和读取预先计算的值更快。换句话说，计算复杂度应该与内存复杂度一起考虑。如果计算成本不高并且可以在缓存中工作，我会保持较小的内存使用量。

但最后，你将不得不测试......

3 回答 3