Menyimpan sedikit vektor dalam memori yang tidak diinisialisasi dan ruang minimal

Trik yang terkenal untuk menyimpan vektor bit menggunakan memori yang tidak diinisialisasi dapat mengalokasikan sedikit vektor ukuran di mana semua bit diatur ke 0 dengan mengalokasikan ( 2 n + 1 ) ⌈ lg n ⌉ bit memori dan menginisialisasi hanya ⌈ lg n ⌉ dari mereka. Representasi ini mendukung pengaturan dan penghapusan bit dalam waktu konstan.$n$$0$$(2 n + 1)\lceil \lg n \rceil$$\lceil \lg n \rceil$

Ini berasal dari buku "Alfred Aho, John Hopcroft, dan Jeffrey Ullman 1974, Desain dan Analisis Algoritma Komputer ... Bab 2, latihan 2.12", "Buku Pemrograman Mutiara Jon Bentley 1986 ... Kolom 1, latihan 8; latihan 9 dalam Edisi Kedua ", dan " makalah Preston Briggs dan Linda Torczon tahun 1993, 'Representasi yang Efisien untuk Perangkat Jarang' " .

"Changing Base without Losing Space" Dodis dkk. Menurunkan persyaratan ruang sedikit ke bit, meskipun algoritma ini membutuhkan perhitungan awal konstanta Θ ( lg n ) dengan Θ ( lg n ) masing-masing bit.$\lceil (2 n + 1) \lg n \rceil + 1$$\Theta(\lg n)$$\Theta(\lg n)$

Berapa banyak ruang yang bisa dihemat? Apakah ada representasi vektor bit di mana

• Bit bisa set atau tidak diset di waktu$O(1)$
• Menginisialisasi vektor bit baru s menggunakan o ( n lg n ) bit memori yang tidak diinisialisasi dan O ( lg n ) memori yang diinisialisasi$0$$o(n \lg n)$$O(\lg n)$

$k$$(2n+1)\lceil \lg n \rceil + kn$

$k=\lceil \lg n \rceil$$k$$\lceil \lg n \rceil$$\lceil n/\lceil \lg n \rceil \rceil$$\Theta(n)$$\Theta(\lg n)$

$O(1)$$\Theta(\lg n)$