在这个链接中，作者说get(index)在Java ArrayList中是O（1），而在LinkedList中是0（n/2），因为它需要遍历到那个条目。ArrayList中花费恒定时间的get操作是有意义的，因为ArrayList可以访问所有索引。但是，我不理解LinkedList的O（n/2）。我被教导的方式是，当你使用大哦符号时，你应该把它写得没有常数，这样更容易向别人解释；即O（n）而不是O（2n）。O（n）不是也是最坏情况运行时间的界吗？这样，使用O（n）对我来说更有意义，因为你正在搜索的元素可能在最后。有人知道作者为什么包括n/2吗？
你说得对，O（n/2）和O（n）完全一样。博客文章的作者可能试图传达LinkedList平均需要遍历n/2个元素才能到达任何特定（随机选择）索引的信息。但这是对big-O表示法的滥用。
公平地说，作者似乎完全意识到O（n）=O（n/2）:
为了从特定索引中删除元素。。。
ArrayList执行使其接近O（n）的复制操作，而LinkedList需要遍历到也使其成为O（n/2）的点
通过使用"也是"，海报似乎承认了这一点。