Algocourselecturenotes: Поправлены заголовки

2020-03-09T11:25:40Z

Поправлены заголовки

← Предыдущая версия		Версия от 11:25, 9 марта 2020
Строка 1:		Строка 1:
	~~== Вектор ==~~		== Операции ==

	=== Операции ===
	Вектор - структура данных, поддерживающая следующие операции:<br>		Вектор - структура данных, поддерживающая следующие операции:<br>
	*Доступ по индексу<br>		*Доступ по индексу<br>
Строка 8:		Строка 6:
	Вышеперечисленные операции должны работать за '''O(1)'''<br>		Вышеперечисленные операции должны работать за '''O(1)'''<br>

	=== Способы реализации вектора ===		== Способы реализации вектора ==
	==== Способ 1 ====		=== Способ 1 ===
	Если известно, что размер структуры в любой момент времени не превышает ''K'', то можно хранить массив на ''K'' элементов<br>		Если известно, что размер структуры в любой момент времени не превышает ''K'', то можно хранить массив на ''K'' элементов<br>

	''Используемая память'' = $ \Theta(K) $ <br>		''Используемая память'' = $ \Theta(K) $ <br>

	==== Способ 2 ====		=== Способ 2 ===
	Будем хранить массив размера ''buffer'', который в дальнейшем будем реаллоцировать. Пусть ''S'' - размер структуры.<br>		Будем хранить массив размера ''buffer'', который в дальнейшем будем реаллоцировать. Пусть ''S'' - размер структуры.<br>

Строка 21:		Строка 19:
	2)''buffer'' гораздо больше, чем ''S'', тогда вектор занимает сильно больше памяти, чем требуется.		2)''buffer'' гораздо больше, чем ''S'', тогда вектор занимает сильно больше памяти, чем требуется.

	===== Решение проблемы 1 =====		==== Решение проблемы 1 ====
	''S'' = ''buffer'', поступает запрос на добавление элемента. Тогда увеличиваем ''bufffer'' в 2 раза: создаём массив в 2 раза больше, копируем в первую половину нового массива весь старый.<br>		''S'' = ''buffer'', поступает запрос на добавление элемента. Тогда увеличиваем ''bufffer'' в 2 раза: создаём массив в 2 раза больше, копируем в первую половину нового массива весь старый.<br>
	'''Время операции''': $ \Theta(''buffer'') $ <br>		'''Время операции''': $ \Theta(''buffer'') $ <br>

	===== Решение проблемы 2 =====		==== Решение проблемы 2 ====
	Если ''S'' меньше ''buffer'' более чем в 4 раза, то уменьшаем ''buffer'' в 2 раза<br>		Если ''S'' меньше ''buffer'' более чем в 4 раза, то уменьшаем ''buffer'' в 2 раза<br>
	'''Время операции''': $ \Theta(''buffer'') $ <br>		'''Время операции''': $ \Theta(''buffer'') $ <br>

	===== Оценка времени =====		==== Оценка времени ====
	Таким образом, $ \frac{1}{4}''buffer'' \leq ''S'' \leq ''buffer'' $, а значит ''buffer'' = O(''S'')<br>		Таким образом, $ \frac{1}{4}''buffer'' \leq ''S'' \leq ''buffer'' $, а значит ''buffer'' = O(''S'')<br>
	Амортизированно, требуемые операции выполняются за O(1), то есть если изначально структура пустая, то любые ''m'' операций выполняются за O(''m'')		Амортизированно, требуемые операции выполняются за O(1), то есть если изначально структура пустая, то любые ''m'' операций выполняются за O(''m'')

Algocourselecturenotes: Новая страница: «== Вектор == === Операции === Вектор - структура данных, поддерживающая следующие операции:
…»

2020-03-08T10:46:23Z

Новая страница: «== Вектор == === Операции === Вектор - структура данных, поддерживающая следующие операции: …»

Новая страница

== Вектор ==

=== Операции ===
Вектор - структура данных, поддерживающая следующие операции: 
*Доступ по индексу 
*Добавление в конец структуры 
*Удаление из конца структуры 
Вышеперечисленные операции должны работать за '''O(1)''' 

=== Способы реализации вектора ===
==== Способ 1 ====
Если известно, что размер структуры в любой момент времени не превышает ''K'', то можно хранить массив на ''K'' элементов 

''Используемая память'' = $ \Theta(K) $ 

==== Способ 2 ====
Будем хранить массив размера ''buffer'', который в дальнейшем будем реаллоцировать. Пусть ''S'' - размер структуры. 

Возникает 2 проблемы: 
1)''S'' = ''buffer'': в этом случае нам некуда добавлять новые элементы 
2)''buffer'' гораздо больше, чем ''S'', тогда вектор занимает сильно больше памяти, чем требуется.

===== Решение проблемы 1 =====
''S'' = ''buffer'', поступает запрос на добавление элемента. Тогда увеличиваем ''bufffer'' в 2 раза: создаём массив в 2 раза больше, копируем в первую половину нового массива весь старый. 
'''Время операции''': $ \Theta(''buffer'') $ 

===== Решение проблемы 2 =====
Если ''S'' меньше ''buffer'' более чем в 4 раза, то уменьшаем ''buffer'' в 2 раза 
'''Время операции''': $ \Theta(''buffer'') $ 

===== Оценка времени =====
Таким образом, $ \frac{1}{4}''buffer'' \leq ''S'' \leq ''buffer'' $, а значит ''buffer'' = O(''S'') 
Амортизированно, требуемые операции выполняются за O(1), то есть если изначально структура пустая, то любые ''m'' операций выполняются за O(''m'')

====== Доказательство амортизированности: cлучай 1 ======
Между двумя командами '''push_back''', требующими реаллокацию, будет хотя бы ''buffer'' операций '''push_back'''. Все эти операции потребуют '''O(''buffer'')''' времени, поделим на ''buffer'', и поймём, что в среднем одна операция выполняется за '''O(1)'''.
====== Доказательство амортизированности: cлучай 2 ======
Между командами '''push_back''' и '''pop_back''', требующими реаллокацию, будет хотя бы $ \frac{''buffer''}{2} $ операций '''pop_back'''. Все эти операции потребуют '''O(''buffer'')''' времени, поделим на ''buffer'', и поймём, что в среднем одна операция выполняется за '''O(1)'''.
====== Доказательство амортизированности: cлучай 3, 4 ======
Остальные случаи рассматриваются аналогично первым двум.

Вектор - История изменений

Algocourselecturenotes: Поправлены заголовки

Algocourselecturenotes: Новая страница: «== Вектор == === Операции === Вектор - структура данных, поддерживающая следующие операции:…»

Algocourselecturenotes: Новая страница: «== Вектор == === Операции === Вектор - структура данных, поддерживающая следующие операции:
…»