Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

У
ПРАЖНЕНИЯ 
 
1. Для каких значений N справедливо 10×N×log
2
N > N
2
?
2. Для каких значений N выражение N
3/2
имеет значение в пределах от 
N× (log
2
N)
2
/2 до 2×N× (log
2
N)
2
? 
3. Докажите, что [log
2
N]+1 – это количество бит, необходимое для 
представления числа N в двоичной форме ([log
2
N] – целая часть ло-
гарифма).
4. Покажите, что N×log
2
N = O(N
3/2
).
14 / 23

---

15 
 
Г
ЛАВА 
2. А
ЛГОРИТМЫ ПОИСКА И СОРТИРОВКИ
 
В разделе описываются основные алгоритмы поиска и сортировки. За-
дача поиска заключается в установлении факта наличия в той или иной 
структуре данных принадлежащих ей элементов, которые обладают некото-
рым наперед заданным свойством. Это свойство называется ключом поиска. 
Как правило, задача поиска входит составной частью в более общую задачу, 
требующую доступа к искомому элементу.
Сортировкой некоторой структуры данных называют процесс переста-
новки ее элементов в определенном порядке. Для сортировки выбирают один 
из параметров, характеризующих эти элементы. Такой параметр называют 
ключом сортировки. Например, в качестве ключа сортировки списка сотруд-
ников может использоваться фамилия сотрудника, а может – год его рожде-
ния.
Цель сортировки заключается в том, чтобы облегчить последующий 
поиск элементов в отсортированной структуре данных. Поэтому элементы 
сортировки и поиска присутствуют почти во всех задачах обработки инфор-
мации. 
В этой главе мы будем рассматривать алгоритмы поиска и сортировки 
на примере одномерных целочисленных массивов. Этого достаточно, чтобы 
продемонстрировать главные особенности этих алгоритмов. Ключом как по-
иска, так и сортировки будем считать значение элемента массива.