O(1)ならたぶんランダムアクセスって言うんだろうけど、O(logN)で各要素にアクセス出来る場合ってランダムアクセス可能って言うんだろうか。
ランダムアクセス(ランダムリード)とは - IT用語辞典 e-Words
メモリやハードディスクなど、今日使われているほとんどの記憶装置はランダムアクセスに対応している。
ディスクがランダムアクセス可能なメディアって話をしてしまうと計算量の概念とは相容れない気がしてきた。
あるいは、速度は関係なくて index アクセス出来れば良いのか。つまり linked list もラッパーを書けばランダムアクセスなデータ構造になる、と。
混乱したので誰かまとめてください。