一個包含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中文網其他相關文章！