- 201 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:49:16.27 ID:EEj8G+es.net]
- C言語であろうがなかろうが言語に関係なくO(1)は無理
わからない人はコーディングすればすぐわかる
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別の配列で保持管理しないといけない
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理する配列で毎回O(n)を必要とする移動が発生
どんな言語でどんな手法を用いてもO(1)は絶対に不可能
