| **Во всех задачах, если это не оговорено особо, размер вспомогательной памяти не должен зависеть от длин векторов, а число действий пропорционально длине вектора (т.е. для x[1..n] это Cn |
1.
Найти для вектора x[1..n] число различных элементов (Число действий Cn)
2.
Найти для x[1..n] и y[1..p] их пересечение, т.е. общие элементы с учетом кратности (Число действий Cn+p)
3.
Для x[1..n], y[1..p] и z[1..q], найти первый общий элемент
4. (cлияние)
Объединить x[1..n] и y[1..p] в z[1..n+p].
5.
Найти для x[1..n] и y[1..p] число различных элементов (Число действий Cn+p)
6.
Сумму вида x[i] + y[j] наиболее близкую к заданному числу a. (Число действий Cn+p; исходные векторы запрещено менять.)
7.
Для вектора x[1..n] найти наименьшее натуральное a, непредставимое в виде суммы каких-либо его элементов.
8. (двоичный поиск)
В x[1..n] найти число заданное a. Количество действий порядка log n