Алгоритмы

Big O - математическое обозначение для сравнения поведений функций.

O описывает насколько быстро работает алгоритм. Используется для сравнения количества операций.

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

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

В порядке возрастания:

• О(1) константная
• О(log(n)) логарифмическая
• O(n) линейная
• O(n*log(n)) квазилинейная
• O(n*n) квадратичная
• O(n^3) кубическая
• O(2^n) экспоненциальная
• O(n!) факториальная

LinkedList в большинстве случаев проигрывает ArrayList, но в оставшемся меньшинстве он вне конкуренции.

LinkedList нужно использовать, когда:
необходимо много данных добавлять в начало списка, удалять с начала, set в конце списка.

ArrayList нужно использовать, когда:

get, set (начало и середина), add, remove

Рекурсия имеет линейную сложность O(n)

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

Виды сортировок:

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

В худшем случае - O(n^2)

В лучшем случае - O(n)

Шейкерная сортировка

Будем идти не только слева направо, но и справа налево. Будем поддерживать два указателя: begin and end, которые будут обозначать, какой отрезок массива еще не отсортирован. На очередной итерации при достижении end вычитаем из него единицу и движемся справа налево, аналогично, при достижении begin прибавляем единицу и двигаемся слева направо. Значения такие же как у пузырьковой сортировки, но в реальности работает лучше.

Сортировка расческой

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

В лучшем случае - O(n*log(n))
В худшем случае - O(n^2)