Занятие 7

Поиск в неотсортированном массиве выполняется за время `O(N)`, а в отсортированном – за `O(log\ N)`. Сортировка может существенно уменьшить время работы программы, в которой часто выполняется поиск.

Если область определения небольшая (до 1000 значений), а найти быстрый алгоритм не удалось, то можно вычислить все ответы на компьютере и послать программу, выводящую готовый ответ из таблицы, хранящейся в программе. При таком способе решения нужно учитывать также ограничения на размер посылаемого исходного кода.

Иногда можно выполнить подготовительные расчеты и сохранить их результаты в специальных структурах данных. Например, при определении простоты большого набора чисел до `10^12` вычислить все небольшие простые числа до `10^6`, а затем использовать только их для проверки, уменьшая таким образом время выполнения на порядок. Другой пример: если нужно часто искать сумму элементов подматрицы, то можно хранить в специальной матрице `S_{ij}` частичные суммы верхней левой части матрицы `A_{ij}`. Значения элементов этой матрицы вычисляются по формуле `S_{ij}=A_{ij}\ +\ S_{i-1j}\ +\ S_{{ij}-1}\ -\ S_{i-1j-1}`. Сумма элементов подматрицы `(i_1,j_1,i_2,j_2)` находится по формуле `S_{i_2j_2}\ -\ S_{i_1-1j_2}\ -\ S_{i_2j_1-1}\ +\ S_{i_1-1j_1-1}`.

Если в программе часто выполняется вычисление какой-либо функции для одних и тех же данных, то можно вместо повторного вычислений запоминать при первом вызове результат в таблице, а при повторном вызове функции с теми же аргументами просто возвращать его.

int _f[100][100];
const int UNDEF=-1;
int f(int a, int b)
{ // 0<=a<100, 0<=b<100
  int r;
  if(_f[a][b]!=UNDEF) return _f[a][b];
  ... // вычислить результат r
  return _f[a][b]=r;
}

При поиске достижимости некоторого состояния из начального за `k` шагов можно получить список всех состояний, достижимых из начального состояния за `k/2`, затем список всех состояний, достижимых из конечного за `k/2` шагов. Затем нужно отсортировать оба списка и сравнить с помощью слияния, встречаются ли среди них одинаковые.