tasks.md

Источник ИТМО

Работа с отсортированными массивами

Даны два отсортированных по неубыванию массива a и b. Определите, есть ли в них одинаковые числа. Время O(n).

Даны два отсортированных по неубыванию массива a и b. Найдите такие i и j, что разница |a[i] − b[j]| минимальна. Время O(n).

Даны два отсортированных по неубыванию массива a и b и число S. Найдите такие i и j, что сумма a[i] + b[j] = S. Время O(n).

Даны два отсортированных по неубыванию массива a и b. Найдите число пар (i, j), таких, что a[i] = b[j]. Время O(n).

Даны два отсортированных по неубыванию массива a и b. Найдите число пар (i, j), таких, что a[i] > b[j]. Время O(n).

Рекуррентные соотношения-2

Докажите по индукции, что если $T(n) = 2T(n/2 + 20) + n$, то $T(n) = O(n \cdot \log{ }n)$.

Докажите по индукции, что если $T(n) = 2T(n/2 + \log{ } n) + n$, то $T(n) = O(n \cdot \log{ } n)$.

Докажите по индукции, что если $T(n) = \log(n) T(n/ \log{ } n) + n$, то $T(n) = O(n \cdot \log{ } n)$.

Докажите по индукции, что если $T(n) = 2T(n/2) + n$, то $T(n) = \Omega(n \cdot \log{ } n)$ (оценка снизу).

Докажите по индукции, что если $T(n) = 2T(\sqrt n) + 1$, то $T(n) = O(\log{ } n)$.

Оценка времени работы

Для каждой из приведенных программ и функций оцените время ее работы

int func(int n) { 
		if (n == 0)  
			return 1; 
		else 
			return func(n / 5) + func(n / 5); 
}

int func2(int n) { 
		if (n == 0)  
			return 1; 
		else 
			return 2*func2(n / 5); 
}

---

Дан массива a. Пара (i, j), такая, что i < j и a[i] > a[j] называется инверсией. Пусть в массиве длины n ровно k инверсий. Докажите, что сортировка вставками работает за O(n + k).

Дан массива a. Найдите число инверсий в нем. Время O(n log n)

Покажите, что при правильной (какой?) реализации сортировка слиянием является устойчивой (то есть, не меняет порядок равных элементов).

Реализуйте сортировку слиянием снизу вверх (без рекурсии).

---