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 중국어 웹사이트의 기타 관련 기사를 참조하세요!