n 個の要素と O(1) 回の演算を含むデータ構造?

ここでは、n 個の要素と O(1) の演算を含むデータ構造を見ていきます。したがって、操作の実行には一定の時間がかかります。

データ構造には n 個の要素 (0 から n-1) が保持されます。データは任意の順序で指定できます。挿入、削除、検索には O(1) 時間がかかります。

この問題を解決するには、ブール配列を使用します。これは、アイテムが場所 i に存在するかどうかを示します。項目が存在する場合は 1、存在しない場合は 0。

アルゴリズム

初期化(n)

begin
   fill all elements of the Boolean array as 0
end

挿入(i)

begin
   set element at index i as 1(true)
end

削除(i)

begin
set element at index i as 0(false)
end

検索(i)

begin
   return item at position i
end

例

//initialization
void init(int n) {
   bool dataStructure[n];
   for (int i = 0; i<n; i++)
      dataStructure[i] = 0;
}
//Insertion
void insert(unsigned i) {
   dataStructure[i] = 1;
}
//Deletion
void delete(unsigned i) {
   dataStructure[i] = 0;
}
//Search
bool search(unsigned i) {
   return dataStructure[i];
}

以上がn 個の要素と O(1) 回の演算を含むデータ構造?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。