抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
初期可能アレイは,任意の要素に対する読取と書き込み操作と全アレイの初期化をサポートするアレイである。本論文は,wビット単語サイズを有する単語RAMモデルに関するNl+1ビットにおけるl|ΔO(w)ビットエントリを含む長さNの初期化可能アレイを実装するための簡単なインプレイアルゴリズムを提案して,この提案アレイは,lビットエントリを含む長さNの通常アレイの上に1つの余分なビットだけを必要とした。著者らのアルゴリズムは,一定の最悪ケース時間におけるすべての3つの操作をサポートして,それは,各々の操作の間,最も一定の数の単語O(w)ビットを用いて,それを実行して実行した。一定の最悪ケース時間[HagerupとKammer,ISAAC 2017]ですべての演算をサポートする余分なビットなしで,初期化可能なアレイの実装がないので,時間と空間の複雑さは最適である。著者らのアルゴリズムは,N+o(N)追加ビットを用いて,一定の最悪ケース時間におけるすべての操作をサポートするために,初期の研究[Navarro,CSUR 2014]で提示された最良のアルゴリズムで有意に改善した。【JST・京大機械翻訳】
