21/11/22 17:18:11.48 EEj8G+es.net
>>185
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)を必要とする移動が発生する
つまりどんな言語でどんな手法でもO(1)は絶対に不可能
21/11/22 17:18:11.48 EEj8G+es.net
>>185
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)を必要とする移動が発生する
つまりどんな言語でどんな手法でもO(1)は絶対に不可能