Skip to content

Files

Latest commit

 Cannot retrieve latest commit at this time.

History

History
576 lines (417 loc) · 35.6 KB

3_algorithms.md

File metadata and controls

576 lines (417 loc) · 35.6 KB

Алгоритмы

Общее определение

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

Основные свойства алгоритмов:

Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).

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

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

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

Различают три основных вида алгоритмов:

Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.

Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.

Примеры типичных алгоритмов в программировании:

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

  • поиск в неупорядоченном множестве данных;
  • поиск в упорядоченном множестве данных.

Упорядоченность – наличие отсортированного ключевого поля.

Сортировка — упорядочение (перестановка) элементов в подмножестве данных по какому-либо критерию. Чаще всего в качестве критерия используется некоторое числовое поле, называемое ключевым. Упорядочение элементов по ключевому полю предполагает, что ключевое поле каждого следующего элемента не больше предыдущего (сортировка по убыванию). Если ключевое поле каждого последующего элемента не меньше предыдущего, то говорят о сортировке по возрастанию. Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве при обработке данных.

Все алгоритмы сортировки делятся на

  • алгоритмы внутренней сортировки (сортировка массивов);
  • алгоритмы внешней сортировки (сортировка файлов).

Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.

Нотация «большое О»

Performance is usually described with the Big O Notation. It defines the limiting behavior of a function and is often used to characterize algorithms on their performance. O defines the upper bound of the growth rate of the function. To see just how big the difference is, see commonly used O notations and the number of operations needed.

For example, if you sort an array with 50 elements, and your sorting algorithm has a complexity of O(n^2), there will be 2,500 operations necessary to complete the task. Furthermore, there’s also overhead in internal management and calling that method - so it’s 2,500 operations times constant. O(1) is the ideal complexity, meaning constant time. Good sorting algorithms usually need O(n log n) time.

Последовательный поиск

linear search

Для неупорядоченного массива – перебор всех элементов, пока либо не найдется элемент, либо не закончится массив. 
/*
	O(n) — в худшем случае (элемент в конце или отсутствует).
	O(1) — в лучшем случае (элемент в начале).
	O(1) — дополнительная память не используется (поиск in-place).
*/
func linearSearch<T: Equatable>(_ array: [T], _ target: T) -> Int? {
    // Corner case: пустой массив
    guard !array.isEmpty else {
        return nil
    }

    // Проходим по всем элементам массива
    for (index, element) in array.enumerated() {
        if element == target {
            return index
        }
    }

    // Элемент не найден
    return nil
}

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

binary search, half-interval search, logarithmic search, binary chop

Алгоритм двоичного поиска похож на то, как мы ищем слово в словаре. Открываем словарь посередине, смотрим в какой из половин будет нужное нам слово. Допустим, в первой. Открываем первую часть посередине, продолжаем половинить, пока не найдем нужное слово. С массивами так: есть упорядоченный массив, берем число из середины массива, сравниваем с искомым. Если оно оказалось больше, значит искомое число в первой половине массива, если меньше — во второй. Продолжаем делить оставшуюся половину, когда находим нужное число возвращаем его индекс, если не находим возвращаем null. 

/// Двоичный поиск в отсортированном массиве.
/// Возвращает индекс найденного элемента или nil, если элемент не найден.
/// - Time Complexity: O(log n)
/// - Space Complexity: O(1) — итеративный подход, не использует стек
func binarySearch<T: Comparable>(_ array: [T], _ target: T) -> Int? {
    // Corner case: пустой массив
    guard !array.isEmpty else {
        return nil
    }

    var left = 0
    var right = array.count - 1

    while left <= right {
        let mid = left + (right - left) / 2

        if array[mid] == target {
            return mid
        } else if target < array[mid] {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    // Элемент не найден
    return nil
}

NSArray has come with built-in binary search since iOS 4 / Snow Leopard:

typedef NS_OPTIONS(NSUInteger, NSBinarySearchingOptions) {
  NSBinarySearchingFirstEqual     = (1UL << 8),
  NSBinarySearchingLastEqual      = (1UL << 9),
  NSBinarySearchingInsertionIndex = (1UL << 10),
};

- (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)range options:(NSBinarySearchingOptions)options usingComparator:(NSComparator)cmp;

Why would you want to use this? Methods like containsObject: and indexOfObject: start at index 0 and search every object until the match is found - they don’t require the array to be sorted but have a performance characteristic of O(n). Binary search, on the other hand, requires the array to be sorted, but only needs O(log n) time. Thus, for one million entries, binary search requires, at most, 21 comparisons, while the naive linear search would require an average of 500,000 comparisons.

Time to search for 1000 entries within 1000000 objects.

Linear: 54130.38[ms].
Binary: 7.62[ms]

For comparison, the search for a specific index with NSOrderedSet took 0.23 ms - that’s more than 30 times faster, even compared to binary search. Keep in mind that sorting is expensive as well. Apple uses merge sort, which takes O(n*log n), so if you just have to call indexOfObject: once, there’s no need for binary search.

Сортировка вставками

insertion sort

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

  • Устойчив
  • Может сортировать массив по мере его поступления
/// Сортирует массив по возрастанию (in-place).
/// - Time Complexity:
///   - O(n²) — в худшем случае (обратная сортировка)
///   - O(n) — в лучшем случае (почти отсортирован)
/// - Space Complexity: O(1) — сортировка на месте, без доп. памяти
func insertionSort<T: Comparable>(_ array: inout [T]) {
    // Corner case: пустой массив или из одного элемента — уже отсортирован
    guard array.count > 1 else { return }

    for i in 1..<array.count {
        var j = i
        let key = array[i]

        // Сдвигаем элементы вправо, пока не найдём место для вставки
        while j > 0 && array[j - 1] > key {
            array[j] = array[j - 1]
            j -= 1
        }

        array[j] = key
    }
}

Сортировка пузырьком

bubble sort, sinking sort

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

  • Эффективен для небольших массивов из-за сложности
/// Сортирует массив по возрастанию (in-place).
/// - Time Complexity:
///   - O(n²) — в худшем и среднем случае
///   - O(n) — в лучшем случае (если массив уже отсортирован, с оптимизацией)
/// - Space Complexity: O(1) — сортировка на месте, без доп. памяти
func bubbleSort<T: Comparable>(_ array: inout [T]) {
    // Corner case: массив из 0 или 1 элемента уже отсортирован
    guard array.count > 1 else { return }

    let n = array.count
    var didSwap: Bool

    // Внешний цикл — проход по всем элементам
    for i in 0..<n {
        didSwap = false

        // Внутренний цикл — всплытие самого большого элемента в конец
        for j in 0..<n - i - 1 {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
                didSwap = true
            }
        }

        // Если на этом проходе не было обменов — массив уже отсортирован
        if !didSwap {
            break
        }
    }
}

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

selection sort

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора. Плюсы:

  • эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
  • эффективен на наборах данных, которые уже частично отсортированы;
  • это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
  • может сортировать список по мере его получения;
  • использует O(1) временной памяти, включая стек.

Минусы:

  • неустойчивый
/// На каждом шаге находит минимальный элемент и ставит его на нужное место.
/// - Time Complexity:
///   - O(n²) — во всех случаях (всегда n проходов и n сравнений каждый)
/// - Space Complexity: O(1) — сортировка in-place, без дополнительной памяти
func selectionSort<T: Comparable>(_ array: inout [T]) {
    // Corner case: массив из 0 или 1 элемента — уже отсортирован
    guard array.count > 1 else { return }

    for i in 0..<array.count - 1 {
        var minIndex = i

        // Находим индекс минимального элемента в оставшейся части массива
        for j in i + 1..<array.count {
            if array[j] < array[minIndex] {
                minIndex = j
            }
        }

        // Меняем местами, если нашли меньший элемент
        if i != minIndex {
            array.swapAt(i, minIndex)
        }
    }
}

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

сортировка Хоара, quicksort, qsort O(n*log(n)) в среднем случае, O(n^2) в худшем случае, разделяй и властвуй

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов. Общая идея алгоритма состоит в следующем:

  1. Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива.
  2. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом — «меньшие опорного», «равные» и «большие».
  3. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

На практике массив обычно делят не на три, а на две части, например, «меньшие опорного» и «равные и большие». Такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.

Достоинства:

  • Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
  • Прост в реализации.
  • Требует лишь O(lg(n)) дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае O(n) памяти)
  • Хорошо сочетается с механизмами кэширования и виртуальной памяти.
  • Допускает естественное распараллеливание (сортировка выделенных подмассивов в параллельно выполняющихся подпроцессах).
  • Допускает эффективную модификацию для сортировки по нескольким ключам (в частности — алгоритм Седжвика для сортировки строк): благодаря тому, что в процессе разделения автоматически выделяется отрезок элементов, равных опорному, этот отрезок можно сразу же сортировать по следующему ключу.
  • Работает на связных списках и других структурах с последовательным доступом, допускающих эффективный проход как от начала к концу, так и от конца к началу.

Недостатки:

  • Сильно деградирует по скорости (до Theta(n^2)) в худшем или близком к нему случае, что может случиться при неудачных входных данных.
  • Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека, так как в худшем случае ей может потребоваться сделать O(n) вложенных рекурсивных вызовов.
  • Неустойчив
/// Быстрая сортировка (Quick Sort) — рекурсивная версия.
/// - Time Complexity:
///   - O(n log n) в среднем
///   - O(n²) в худшем (если выбрать плохой опорный элемент)
/// - Space Complexity:
///   - O(n) — из-за копирования массивов и рекурсии
func quickSort<T: Comparable>(_ array: [T]) -> [T] {
    // Corner case: массив из 0 или 1 элемента — уже отсортирован
    guard array.count > 1 else { return array }

    let pivot = array[array.count / 2] // Опорный элемент (середина)
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }

    // Рекурсивно сортируем меньшие и большие части
    return quickSort(less) + equal + quickSort(greater)
}

Рекурсивная функция

Функция, вызывающая саму себя. Вопрос о желательности использования рекурсивных функций в программировании неоднозначен: с одной стороны, рекурсивная форма может быть структурно проще и нагляднее, в особенности, когда сам реализуемый алгоритм по сути рекурсивен. Кроме того, в некоторых декларативных или чисто функциональных языках (таких как Пролог или Haskell) просто нет синтаксических средств для организации циклов, и рекурсия в них — единственный доступный механизм организации повторяющихся вычислений. С другой стороны, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии. Так, широко распространённый в учебной литературе пример рекурсивного вычисления факториала является, скорее, примером того, как не надо применять рекурсию, так как приводит к достаточно большой глубине рекурсии и имеет очевидную реализацию в виде обычного циклического алгоритма.

Плюсы

  • Наглядность
  • Простота

Минусы

  • Возможна большая глубина рекурсии, из-за которой может произойти быстрое переполнение стека и нехватка памяти.

Факториал

// O(n) сложность
// O(n) память
func factorialRecursive(_ n: Int) -> Int {
    guard n >= 0 else {
        fatalError("Факториал определен только для неотрицательных чисел.")
    }
    return n == 0 ? 1 : n * factorialRecursive(n - 1)
}

// O(n) сложность
// O(1) память
func factorialIterative(_ n: Int) -> Int {
    guard n >= 0 else {
        fatalError("Факториал определен только для неотрицательных чисел.")
    }
    var result = 1
    for i in 1...n {
        result *= i
    }
    return result
}

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

  1. Риск переполнения стека вызовов

Рекурсивный алгоритм вызывает себя на каждом шаге, добавляя каждый вызов в стек. Для больших значений n, таких как n = 10,000, это может привести к StackOverflowError из-за ограничения размера стека вызовов. Для больших значений n, каждый вызов занимает место в стеке, что может вызвать ошибки, если стек переполнится.

  1. Больше накладных расходов

Каждый рекурсивный вызов имеет накладные расходы, связанные с:

• Сохранением контекста функции в стеке.

• Обработкой возврата после завершения каждого вызова.

Это делает рекурсивный алгоритм менее эффективным, чем итеративный, который выполняется в одном контексте.

  1. Низкая производительность

Рекурсивный алгоритм имеет такую же временную сложность, как и итеративный (O(n)), но его накладные расходы на управление стеком делают его менее производительным. Итеративный алгоритм выполняется быстрее, так как избегает этих дополнительных операций.

  1. Сложности с отладкой

Глубокая рекурсия усложняет отладку, так как стектрейсы становятся длинными, а отслеживание состояния переменных становится сложным. Это особенно важно в приложениях с большими входными данными.

Преимущество итеративного подхода:

  1. Итеративный алгоритм работает быстрее и использует меньше памяти, так как он не использует стек вызовов.

  2. Этот подход требует постоянного количества памяти (O(1)) и лучше подходит для больших значений n.

Когда использовать рекурсию?

Рекурсивный алгоритм имеет свои плюсы:

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

Однако для больших значений n он неэффективен.

Итог:

Рекурсивный алгоритм факториала менее предпочтителен из-за рисков переполнения стека, накладных расходов и низкой производительности. Итеративный подход или оптимизированные методы (например, через циклы или tail-recursion optimization) более предпочтительны в реальных приложениях.

Последовательность Фибоначчи

// O(2^n) сложность
// O(n) память
func fibonacciRecursive(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}

// O(n) сложность
// O(1) память
func fibonacciIterative(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    var a = 0
    var b = 1
    
    for _ in 2...n {
        let temp = a + b
        a = b
        b = temp
    }
    
    return b
}

How to merge two sorted arrays into a sorted array?

public static int[] merge(int[] a, int[] b) {
  int[] answer = new int[a.length + b.length];
  int i = 0, j = 0, k = 0;

  while (i < a.length && j < b.length) {
    if (a[i] < b[j])       
    answer[k++] = a[i++];

    else        
    answer[k++] = b[j++];               
  }

  while (i < a.length)  
  answer[k++] = a[i++];

  while (j < b.length)    
  answer[k++] = b[j++];

  return answer;
}

Удаление дубликатов из отсортированного массива

Задача: на входе отсортированный массив nums. Удалить дубликаты на месте, вернуть количество уникальных элементов.

Используем два указателя:

• read — читает текущий элемент;

• write — записывает уникальные элементы.

func removeDuplicates(_ nums: inout [Int]) -> Int {
    guard nums.count > 1 else { return nums.count }

    var write = 1

    for read in 1..<nums.count {
        if nums[read] != nums[read - 1] {
            nums[write] = nums[read]
            write += 1
        }
    }

    return write
}

Проверка палиндрома

Задача: проверить, является ли строка палиндромом (одинаково читается слева и справа). Игнорируем регистр и неалфавитные символы.

Используем два указателя: слева и справа, сравниваем символы.

/// Время: O(n)
///	Память: O(n) (фильтрация строки)
func isPalindrome(_ s: String) -> Bool {
    let characters = Array(s.lowercased().filter { $0.isLetter || $0.isNumber })
    var left = 0
    var right = characters.count - 1

    while left < right {
        if characters[left] != characters[right] {
            return false
        }
        left += 1
        right -= 1
    }

    return true
}

Поиск пары с заданной суммой

Поиск пары с заданной суммой

Используем хеш-множество (Set): сохраняем target - num и проверяем, встречалось ли это ранее.

/// Время: O(n)
///	Память: O(n)
func hasPairWithSum(_ nums: [Int], target: Int) -> Bool {
    var seen = Set<Int>()

    for num in nums {
        let complement = target - num
        if seen.contains(complement) {
            return true
        }
        seen.insert(num)
    }

    return false
}