Java for Beginner

Святой JVM! Что за ересь?😂

https://t.me/Java_for_beginner_dev

#Mems

129 views10:25

Основные типы и виды алгоритмов

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

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

int linearSearch(int[] array, int x) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == x) {
            return i;
        }
    }
    return -1;
}
Сложность: O(n). Если массив содержит n элементов, в худшем случае потребуется n операций для поиска.

Бинарный поиск
Бинарный поиск используется для поиска в отсортированном массиве. Алгоритм делит массив пополам на каждой итерации, уменьшая область поиска. Этот алгоритм имеет логарифмическую сложность O(log n), так как количество операций растет логарифмически относительно размера входных данных.

int binarySearch(int[] array, int x) {
    int left = 0, right = array.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == x)
            return mid;
        if (array[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}
Сложность: O(log n). Например, для массива из 1000 элементов потребуется примерно 10 операций в худшем случае.

2. Сортировочные алгоритмы

Сортировка данных — одна из ключевых задач в программировании. Приведем примеры с разной сложностью.

Сортировка пузырьком
Этот метод сравнивает соседние элементы и меняет их местами, пока массив не будет отсортирован. Сложность алгоритма — квадратичная O(n²), что делает его неэффективным для больших массивов.

void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}
Сложность: O(n²). Для массива из 100 элементов потребуется до 10,000 операций в худшем случае.

Быстрая сортировка (QuickSort)
Этот алгоритм использует стратегию «разделяй и властвуй». Он выбирает опорный элемент (pivot), сортирует элементы относительно него, затем рекурсивно повторяет процесс для подмассивов. Сложность в среднем — O(n log n), но в худшем случае (если опорный элемент всегда оказывается крайним) — O(n²).

int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return i + 1;
}

void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int pi = partition(array, low, high);
        quickSort(array, low, pi - 1);
        quickSort(array, pi + 1, high);
    }
}
Сложность: В среднем O(n log n), в худшем случае O(n²). Например, для массива из 1000 элементов потребуется порядка 10,000 операций в среднем случае и до 1,000,000 операций в худшем.

3. Алгоритмы работы с графами

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

Поиск в глубину (DFS)
DFS — это рекурсивный алгоритм, который исследует узлы до максимальной глубины перед возвратом и исследованием других путей. Сложность алгоритма составляет O(V + E), где V — количество узлов, а E — количество ребер.

void DFS(int v, boolean[] visited, List<List<Integer>> adj) {
    visited[v] = true;
    System.out.print(v + " ");
    for (int x : adj.get(v)) {
        if (!visited[x]) {
            DFS(x, visited, adj);
        }
    }
}
Сложность: O(V + E). В зависимости от плотности графа, сложность может быть линейной или близкой к квадратичной.

#Java #Training #Medium #Algorithm

119 views14:25