1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
\documentclass[11pt]{article}
\usepackage{../intro}
\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
\rhead{\color{gray} \small \textit{аисд-1}}
\title{Алгоритмы и структуры данных 1}
\usepackage{ctable}
% -- Here bet dragons --
\begin{document}
\maketitle
\drawcat{50pt}
\clearpage
\newcommand{\funcname}[1]{
{\incons
\textbf{#1}}
}
\newcommand{\len}[1]{\mathrm{len}\!\left( #1 \right)}
\dmquestion{1}
Понятно, что \funcname{Insert} и \funcname{Increment} работают за $O(1)$ всегда.
Если в \funcname{RemoveLargeElements} мы попадаем в цикл, то все работает за $O(\mathrm{len}(list))$, поскольку мы пробегаем весь лист и делаем что-то константное (подразумевается, что удаление работает за константу), что и является худшим случаем.
\medskip
Докажем, что амортизированно \funcname{RemoveLargeElements} работает за $O(1)$.
Давайте в \funcname{Insert} и \funcname{Increment} класть в банк по $20$ монеток (функции при этом все еще будут работать за константу).
Когда мы вызовем \funcname{RemoveLargeElements}, мы проверим самое первое условие. Если оно не выполнено, мы сразу вернемся и не потратим монеток. Если же оно выполнено, то мы имеем следующее неравенство:
\begin{align*}
maxItem > \left\lceil \frac{\mathrm{len}(list)}{3} \right\rceil\\
maxItem \cdot 3 + 3 > \mathrm{len}(list)
\end{align*}
Тогда за максимальный элемент мы инкрементировали $\frac{maxItem - 1}{2}$ раз, а значит, в банке за этот элемент лежит
\[
20 + \frac{maxItem - 1}{2} \cdot 20 = 10 + maxItem \cdot 10
\] монет.
Их, конечно же, больше, чем $\mathrm{len}(list)$ штук (даже больше, чем в $3$ раза больше), поэтому нам их хватит, чтобы оплатить цикл (на самом деле монет там лежит $O(\mathrm{len}(list))$, поэтому выбрав подходящее количество монет вместо $20$, мы можем оплатить любой линейный цикл). Заметим, что этот самый большой элемент сразу же и удалится, поэтому мы можем смело тратить эти монеты и мы не трогали монеты, отданные за другие элементы.
Поэтому $n$ операций над этой структурой работают за $O(n)$ по времени.
\dmquestion{2}
Примерно алгоритм: будем использовать два стека для ``симуляции очереди'': один стек растет ``в одну'' сторону, а другой в другую (назовем эти два стека главными). Середина очереди в среднем будет на стыке между двумя стеками, а если нам надо будет сделать \funcname{pop\_*} с той стороны, с которой стек пуст, мы за $O(\mathrm{len}(queue))$ перекинем примерно половину элементов в пустой стек с помощью третьего стека (назовем его вспомогательным). Во все остальное время третий стек будет пустым.
\medskip\medskip\medskip
Будем хранить банк монеток, а при каждом \funcname{push\_*} класть в банк $3$ монетки. Мне нужен будет такой инвариант: в банке всегда есть столько монеток:
\[
3 \cdot \max( \len{main\_stack_1}, \len{main\_stack_2} )
\]
Понятно, что после \funcname{push\_*} такой инвариант сохраняется. Теперь покажем, что он сохраняется и для \funcname{pop\_*}.
Если нам надо сделать \funcname{pop\_*} с той стороны, с которой главный стек еще не пуст, то просто запомним для этого стека \funcname{top()}, сделаем \funcname{pop()} и вернем запомненное значение. Количество монет в банке не поменялось.
Теперь если нам надо сделать \funcname{pop\_*} с той стороны, с которой стек пуст,
то перекинем примерно половину элементов в пустой стек из непустого.
Назовем пустой главный стек $s_e$, а непустой - $s_f$. Тогда, так как $s_e$ пуст,
то по инварианту в банке не меньше $3\cdot \len{s_f}$ монеток.
Для удобства, если $\len{s_f}$ нечетно, то засунем в $s_f$ фиктивный элемент.
Итак, мы хотим перекинуть ровно половину элементов из непустого стека в пустой, сохранив порядок. сделаем это с помощью третьего стека.
Изначально у нас три стека:
\begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|}
\hline
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
\hline
\hline
&&&&&&&\\
\hline
\hline
&&&&&&&\\
\hline
\end{tabular}
\medskip
Потратим $\frac{1}{2}\cdot \len{s_f}$ монеток
\begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|}
\hline
1 & 2 & 3 & 4 & & & &\\
\hline
\hline
&&&&&&&\\
\hline
\hline
8 & 7 & 6 & 5 & &&&\\
\hline
\end{tabular}
\medskip
И ещё $\frac{1}{2}\cdot \len{s_f}$ монеток
\begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|}
\hline
&&& & & & &\\
\hline
\hline
4 & 3 & 2 & 1 &&&&\\
\hline
\hline
8 & 7 & 6 & 5 &&&&\\
\hline
\end{tabular}
\medskip
В последний раз $\frac{1}{2}\cdot \len{s_f}$ монеток
\begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|}
\hline
5 & 6 & 7 & 8 & & & &\\
\hline
\hline
4 & 3 & 2 & 1 &&&&\\
\hline
\hline
&&& &&&&\\
\hline
\end{tabular}
\medskip
Мы потратили $\frac{3}{2} \len{s_f}$ монет и осталось столько же. Но так как теперь длина каждого из кусков в два раза меньше, то инвариант сохранился.
Таким образом, \funcname{pop\_*} тоже амортизированно выполняется за $O(1)$.
\clearpage
\dmquestion{3}
Посчитаем для данной длины $n$ максимальную возможную стоимость $k$ бинпоиска на этом массиве.
То есть при всевозможных входных данных длины $n$ мы запустим бинпоиск, который будет работать $k_i$ шагов и возьмем $k = \sup k_i$.
Понятно, что $k = O(\log n)$
{
\color{gray}
здесь надо доказать асимптотику бинпоиска, но я притворюсь, что это мы уже знаем.
}
Теперь выдадим каждому элементу $k$ монеток и на каждый бинпоиск будем тратить монетки, принадлежащие элементу. который мы нашли. Нам всегда хватит столько монеток, потому что бинпоиск на массиве меньшего размера, очевидно, занимает не больше операций, чем на массиве большего размера. Тогда все вместе будет работать за $n * k = O(n \log n)$
\end{document}
|
