Подмножества множества $\{1\ldots n\}$


$\scriptstyle{\blacktriangleright}$ 6.3.1. Используя память O(n) [= пропорциональную n ], хранить подмножества множества $\{1\ldots n\}$:

 \begin{displaymath} \begin{tabular} {ll} Операции & Число действий \\ [1ex] С... ...имальный элемент & $Cn$\\ Проверка пустоты & $Cn$\end{tabular}\end{displaymath}

Решение. Храним множество как array [1..n] of Boolean.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 6.3.2. То же, но проверка пустоты должна выполняться за время C .

Решение. Храним дополнительно количество элементов.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 6.3.3. То же при следующих ограничениях на число действий:

\begin{displaymath} \begin{tabular} {ll} Операции & Число действий \\ [1ex] Сд... ...инимальный элемент & $C$\\ Проверка пустоты & $C$\end{tabular}\end{displaymath}

Решение. Дополнительно храним минимальный элемент множества.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 6.3.4. То же при следующих ограничениях на число действий:

\begin{displaymath} \begin{tabular} {ll} Операции & Число действий \\ [1ex] Сд... ...инимальный элемент & $C$\\ Проверка пустоты & $C$\end{tabular}\end{displaymath}

Решение. Храним минимальный, а для каждого -- следующий и предыдущий по величине.$\scriptstyle\blacktriangleleft$


pvv
1/8/1999