ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
23
Поскольку в рассматриваемой выше задаче приоритетом является
произвольный доступ, то применение структуры FastArray не доста-
точно эффективно.
Структура
IgushArray
—
структура с произвольным доступом,
которая как массив имеет быструю константную операцию доступа,
но сложность операции вставки или удаления составляет всего лишь
O
(
N
1/2
).
Структура может рассматриваться как «быстрый массив» или
«
массив с быстрой операцией вставки». Сложность выполнения опе-
рации определяется как зависимость ее времени выполнения от ко-
личества элементов массива. Время выполнения операций для раз-
личных структур данных приведено в табл. 1 [1].
Таблица 1
Время выполнения операций для различных структур данных
Операция
Массив
IgushArray
FastArray
Список
Доступ
O
(1)
O
(1)
O
(
log
N
)
O
(
N
)
Вставка
O
(
N
)
O
(
N
1/2
)
O
(
log
N
)
O
(1)
Удаление
O
(
N
)
O
(
N
1/2
)
O
(
log
N
)
O
(1)
Вставка:
в конец
O
(1)
O
(1)
O
(
log
N
)
O
(1)
в начало
O
(
N
)
O
(
N
1/2
)
O
(
log
N
)
O
(1)
Примечание.
Выделенные показатели лучше аналогичных показателей стан-
дартного массива.
IgushArray — массив указателей размером приблизительно
N
1/2
.
Каждый элемент массива указывает на очередь с двумя концами раз-
мером около
N
1/2
.
Все очереди имеют одинаковый размер за исклю-
чением последней (может иметь размер меньше
N
1/2
).
Логическое представление
{
}
0 1
1
, , ...,
,
N
I E E E
−
=
где
I
—
структура IgushArray;
k
E
—
элемент логической структуры;
N
—
количество элементов в структуре.
Физическое представление
{
}
0 1
1
, , ...,
,
V
S
I V D D D
−
= =
где
V
—
массив указателей на очереди;
i
D
–
очередь с двумя конца-
ми,
,0 ,1
,
1
{ ,
, ...,
},
Di
i
i
i
i S
D E E E
−
=
,
i j
E
—
элемент физической структу-
ры;
,
1
Di
i j
iS
E E
+
=
—
связь логического и физического представле-
ния;
V
S
—
размер массива указателей;
i
D
S
—
размер очереди.
Параметры физического представления следующие:
0
1
2
SV
D D D
S S S
−
= =
—
все очереди имеют одинаковый размер;
1
SV
D
D
S
S
−
≤
—
последняя очередь может иметь меньший размер;