Конспект книги А. Бхаргава "Грокаем алгоритмы"

Что такое алгоритм?

Набор инструкций для выполнения некоторой задачи.

$О$-большое

Специальная нотация которая описывает скорость выполнения алгоритма, а именно показывает с какой скоростью растет время выполнения алгоритма при увеличении входных данных.

$О$-большое не сообщает скорость в секундах а позволяет сравнить количество операций.
$О$-большое определяет время выполнения в худшем случае.

Разновидности:

• $O(1)$ - постоянное время
• $O(log(n))$ - логарифмическое время. Пример: бинарный поиск
• $O(n)$ - линейное время. Пример: простой поиск
• $O(n * log(n))$ - Пример: эффективные алгоритмы
• $O(n^2)$ - Пример: медленные алгоритмы сортировки (сортировка выбором)
• $O(n!)$ - Пример: очень медленные алгоритмы (задача о коммивояжере)

Линейный поиск

Проходим по массиву и при нахождении первого элемента с искомым значением возвращаем его индекс.

int[] arr = {1, 3, 12, 4, 6, 10, 12, 12, 15, 20, 25};
int index = lineSearch(arr, 12);
System.out.println(index);
System.out.println(arr[index]);

static int lineSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    
    // return -1
    throw new RuntimeException("Key '" + key + "' is not found!");
}

Сложность алгоритма - $O(n)$.
Скорость каждой итерации $O(1)$.
В худшем случай $n$ итераций.

Бинарный поиск

• работает когда список отсортирован

Аналогично поиску слова в словаре.

Реализация через цикл:

static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (key < arr[mid]) {
            high = mid - 1;
        } else if (key > arr[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Реализация через рекурсию:

int[] arr = {1, 3, 12, 4, 6, 10, 12, 12, 15, 20, 25};
int index = binarySearch(arr, 12, 0, arr.length - 1);

static int binarySearch(int[] arr, int key, int low, int high) {
    int mid = low + (high - low) / 2;
    if (high < low) {
        return -1;
    }
    if (arr[mid] == key) {
        return mid;
    } else if (key < arr[mid]) {
        return binarySearch(arr, key, low, mid - 1);

    } else {
        return binarySearch(arr, key, mid + 1, high);
    }
}

Сложность алгоритма - $O({log_{2}(n)})$.

${log_{2}(n)} = k$
$k$ - в какую степень надо возвести 2, чтобы получить n

$n={2^k}$

• если число n - не степень двойки, то выбирается такое наименьшее k, что $2^k > n$.

• $O({log_{2}(n)})$ лучше чем O(n).

Сортировка выбором

public static void main(String args[]) throws Exception {
    int[] arr = {64, 42, 73, 41, 32, 53, 16, 24, 57, 42, 74, 55, 36};
    System.out.println(Arrays.toString(selectionSort(arr)));
}

static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int ind = smallest(arr, i);
        int temp = arr[i];
        arr[i] = arr[ind];
        arr[ind] = temp;
    }
    return arr;
}

static int smallest(int[] arr, int start) {
    int index = start;
    int smallest = arr[start];
    for (int i = start; i < arr.length; i++) {
        if (arr[i] < smallest) {
            smallest = arr[i];
            index = i;
        }
    }
    return index;
}

Сложность алгоритма - $O(n^2)$.

Рекурсия

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

 static int factorial(int n) {
    if (n == 1) {
        return n;
    } else {
        return n * factorial(n - 1);
    }
}

Стратегия "Разделяй и властвуй"

Данная стратегия состоит из двух шагов:

1. Определяется базовый случай - простейший случай из всех возможных.
2. Задача делится или сокращается до тех пор, пока не будет сведена к базовому случаю.

Стратегия "Разделяй и властвуй" - это не алгоритм, это подход к решению задачи.

Пример:

Имеется массив {2, 4, 6}. Нужно просуммировать все числа и вернуть сумму.

static int sum(int[] arr) {
    if (arr.length == 0) {
        return 0;
    } else if (arr.length == 1) {
        return arr[0];
    } else {
        int[] newArr = Arrays.copyOfRange(arr, 1, arr.length);
        return arr[0] + sum(newArr);
    }
}

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

Быстрая сортировка

• Работает быстрее сортировки выбором.
• Основана на стратегии "Разделяй и властвуй"

Базовый случай: массивы с одним элементом или пустой массив

Шаги рекурсивного случая:

1. Выбрать опорный элемент.
2. Разделить массив на два подмассива:
   • элементы, меньшие опрного
   • элементы, большие опорного

public static void quickSort(int[] arr, int from, int to) {
    if (from < to) {

        int divideIndex = partition(arr, from, to);

        quickSort(arr, from, divideIndex - 1);

        quickSort(arr, divideIndex, to);
    }
}

private static int partition(int[] arr, int from, int to) {
    int rightIndex = to;
    int leftIndex = from;

    int pivot = arr[from + (to - from) / 2];
    while (leftIndex <= rightIndex) {

        while (arr[leftIndex] < pivot) {
            leftIndex++;
        }

        while (arr[rightIndex] > pivot) {
            rightIndex--;
        }

        if (leftIndex <= rightIndex) {
            swap(arr, rightIndex, leftIndex);
            leftIndex++;
            rightIndex--;
        }
    }
    return leftIndex;
}

private static void swap(int[] array, int index1, int index2) {
    int tmp  = array[index1];
    array[index1] = array[index2];
    array[index2] = tmp;
}

Хеш-таблицы

Хеш-функция представляет собой функцию которая получает строку¹ и возвращает число. Хеш функция должна соответствовать требованиям:

• Она должна быть последовательной. Всегда возвращать одинаковое число на одну и ту же строку.
• Разным словам должны соотвествовать разные числа.

Массив который хранит элементы при помощи хеш-функций называется хеш-таблицей. Их также называют "ассоциативным массивом", "словарем", "отображением", "хеш картой" или просто "хеш". Хеш таблицы упрощают моделировние отношений между объектами.

HashMap<String, Double> book = new HashMap();
book.put("apple", 0.67);
book.put("milk", 1.49);
book.put("avocado", 1.49);
System.out.println(book.get("avocado"));

Хеши подходят для решения следующих задач:

• моделирование отношений между объектами;
• устранение дубликатов;
• кеширование/запоминание данных вместо выполнения работы на сервере.

Коллизии

Ситуация когда несколько элементов по хешу попадают в одну и туже ячейку².

Одна из стратегий обработки коллизий:

Если несколько ключей отображаются на один элемент, в этом элементе создается связанный список. Но если все элементы попадают в одну ячейку и содержатся в одном связанном списке то работа с данными замедляется.

Отсюда следует:

• Выбор хеш-функции действительно важен. В идеале хеш функция должна распределять ключи равномерно по всему хешу.
• Если связанные списки становятся слишком длинными, то работа с хеш-таблицей сильно замедлится. Но они не станут длинными при использовании хорошей хеш-функции!

Для предотвращения коллизий необходимы:

• низкий коэфициент заполнения;
• хорошая хеш-функция;

Поиск в ширину

Алгоритм для решения задачи поиска кратчайшего пути называется поиском в ширину.

Граф

Граф моделирует набор связей. Каждый граф строится из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называют соседями.

Алгоритм поиска в ширину может ответить на 2 вопроса:

1. существует ли путь от узла А к узлу В?
2. как выглядит кратчайший путь от узла А к узлу В?

Связи первого уровня добавляются в список поиска раньше связей второго уровня и т.д.

Проверять связи необходимо в порядке их добавления. Для операций такого рода есть специальная структура данных, называемая очередью.

Очередь

Для этой структуры данных доступно только две операции:

• постановка в очередь;
• извлечение из очереди;

Элементы добавленные в очередь первыми, первыми же будут из нее извлечены.

Очередь относится к категории структур данных FIFO: First In, First Out ("первым вошел, первым вышел").

А стек принадлежит к категории LIFO: Last In, First Out ("последним вошел, первым вышел").

Реализация графа

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

HashMap<String, String[]> book = new HashMap();
String[] siblings = {"alice", "bob", "claire"};
book.put("you", siblings);

Различают направленный и ненаправленный граф.
Направленный граф (ориентированный, орграф) - это граф в котором отношения действуют только в одну сторону.
Ненаправленный граф (неориентированный, неорграф) - направления отношений нет и каждый из узлов является соседом друг к другу.

Алгоритм графа: 1. Создать очередь 2. Извлечь из очереди первый элемент 3. Выполнить поисковую проверку 4. Если элемент соотвествует поиску закончить проверку, если нет то добавить всех соседей данного элемента в очередь 5. Повторить шаги пока не закончится очередь либо элемент удолетворяющий поиску не будет найден.

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

public static void main(String[] args) {
    HashMap<String, String[]> all = new HashMap();
    String[] siblings = {"alice", "bob", "claire"};
    String[] claireSiblings = {"jack", "steve", "bob"};
    String[] bobSiblings = {"claire", "damon"};
    all.put("you", siblings);
    all.put("claire", claireSiblings);
    all.put("bob", bobSiblings);

    ArrayDeque<String> searchDeque = new ArrayDeque();
    searchDeque.addAll(Arrays.asList(all.get("you")));
    if (!searchMangoSeller(all, searchDeque)) {
        throw new RuntimeException("Mango seller is not found!");
    }
}

static boolean searchMangoSeller(HashMap<String, String[]> all,
                                    ArrayDeque<String> searchDeque) {
    ArrayList<String> searched = new ArrayList();
    while (!searchDeque.isEmpty()) {
        String person = searchDeque.pop();
        if (!searched.contains(person)) {
            if (isSeller(person)) {
                System.out.println(person + " is a mango seller!");
                return true;
            } else {
                String[] siblings = all.get(person);
                if (siblings != null) {
                    searchDeque.addAll(Arrays.asList(siblings));
                }
                searched.add(person);
            }
        }
    }
    return false;
}

static boolean isSeller(String person) {
    return person.charAt(person.length() - 1) == 'n';
}

Время выполнения:

Если поиск выполнен по всей сети то значит вы прошли по каждому ребру $O(количество\:ребер)$.
Также в программе должна храниться очередь поиска. Добавление каждого человека потребует $O(количество\:людей)$. В итоге поиск в ширину займет $O(количество\:людей + количество\:ребер)$, что обычно записывается как $O(V+E)$, V - кол-во вершин, E - кол-во ребер.

Алгоритм Дейкстры

Алгоритм поиска в ширину находит путь, состоящий из меньшего количества сегментов. Но если нужно найти наименьший путь с учетом определеных характеристик, то эту задачу решает Алгоритм Дейкстры.

Алгоритм Дейкстры состоит из следующих шагов:

1. Каждому ребру нужно назначить свой вес, в зависимости от иследуемой характеристики.
2. Найти узел с наименьшей стоимостью.
3. Проверить существует ли более дешевый путь к соседям этого узла и если существует, обновить их стоимости.
4. Повторять, пока это не будет сделано для всех узлов графа.
5. Вычислить итоговый путь.

Граф с весами называется взвешенным графом. Граф без весов называется невзвешенным графом.

Для вычисления кратчайшего пути в невзвешенном графе используется поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры.

В графах также могут присутствовать циклы. Это означает, что вы можете начать с некоторого узла перемещаться по графу, а потом снова оказаться в том же узле.

В ненаправленном графе, каждый из двух узлов ведет к другому узлу, а это цикл!
Поэтому, алгоритм Дейкстры работает только с направленными ациклическими графами, DAG (Directed Acyclic Graph).

Работа с отрицательным весом

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

Однако Алгоритм Дейкстры не может использоваться при наличии ребер имеющих отрицательный вес. Такие ребра нарушают работу алгоритма. Если вы хотите найти кратчайший путь в графе, содержащем ребра с отрицательным весом, для этого существует специальный алгоритм, называемый алгоритмом Беллмана-Форда.