java - ArrayList 恒定时间和线性时间访问

Question

我一直在学习 Java SE 7 的技巧。我已经阅读了关于 ArrayList 的声明。 :

• 访问在恒定时间内执行。
• 插入/删除在线性时间内执行。

我想知道什么是恒定和线性时间访问？

Answer 1

恒定时间意味着每个操作执行所需的时间有一个硬性界限。

线性时间意味着ArrayList越长是(它包含的对象越多)操作将花费的时间越长。连接是线性的，即 time(op) <= CONST * #elements

在复杂性分析中，我们将其称为big O notation线性时间是O(n) , 常数时间为 O(1)

---

原因是:

• 访问是普通数组访问，并且在 RAM 机器(例如 PC)中以恒定时间完成。
• 插入/删除 - 如果它不在最后一个元素中，则需要移动所有以下元素:(插入需要向右移动，删除需要向左移动) - 因此您实际上需要线性数量的 OP 来执行插入/删除(除非是最后一个元素)