Java for Beginner
696 subscribers
605 photos
165 videos
12 files
942 links
Канал от новичков для новичков!
Изучайте Java вместе с нами!
Здесь мы обмениваемся опытом и постоянно изучаем что-то новое!

Наш YouTube канал - https://www.youtube.com/@Java_Beginner-Dev

Наш канал на RUTube - https://rutube.ru/channel/37896292/
Download Telegram
Алгоритмы

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

Особенности Алгоритмов

Четкость и Однозначность:
Каждый шаг алгоритма должен быть ясно определен без двусмысленности.
Конечность: Алгоритм должен завершаться после конечного числа шагов.
Эффективность: Алгоритм должен использовать минимальные ресурсы — время и память.
Масштабируемость: Эффективность алгоритма должна сохраняться при увеличении объема входных данных.


Наиболее распространенный способ описания сложности алгоритма — это нотация "О" (Big-O). Она позволяет определить, как количество операций, необходимых для выполнения алгоритма, увеличивается с увеличением размера входных данных. Разберем наиболее важные типы сложности.

O(1) — Константная сложность

Алгоритмы с константной сложностью выполняются за фиксированное время, независимо от размера входных данных. Примером может служить доступ к элементу массива по индексу:
int[] array = {1, 2, 3, 4, 5};
int element = array[2]; // O(1)

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

O(n) — Линейная сложность

Алгоритмы с линейной сложностью увеличивают время выполнения пропорционально размеру входных данных. Примером является простая итерация по массиву:
int[] array = {1, 2, 3, 4, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}

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


O(n²) — Квадратичная сложность

Алгоритмы с квадратичной сложностью увеличивают время выполнения пропорционально квадрату размера входных данных. Примером является сортировка пузырьком:
int[] array = {5, 1, 4, 2, 8};
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}

Сложность: O(n²).
Лучший случай: массив уже отсортирован, минимальное количество операций (O(n)).
Средний случай: частично отсортированный массив — требует больше операций, чем в лучшем случае, но меньше, чем в худшем (O(n²)).
Худший случай: элементы массива полностью упорядочены в обратном порядке, требующий максимального количества операций (O(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).
Лучший случай: элемент найден в середине массива на первой итерации (O(1)).
Средний случай: несколько итераций, но элемент найден до достижения последнего деления (O(log n)).
Худший случай: элемент отсутствует или находится на одном из концов массива, требуя полного деления массива до его минимального размера (O(log n)).


Лучший, средний и худший варианты выполнения

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


#Java #Training #Medium #Algorithm
September 9, 2024
September 9, 2024
Поиск в ширину (BFS)
BFS использует очередь и исследует граф уровнями, начиная с начального узла. Как и DFS, сложность BFS — O(V + E).
void BFS(int v, boolean[] visited, List<List<Integer>> adj) {
Queue<Integer> queue = new LinkedList<>();
visited[v] = true;
queue.add(v);
while (!queue.isEmpty()) {
v = queue.poll();
System.out.print(v + " ");
for (int x : adj.get(v)) {
if (!visited[x]) {
visited[x] = true;
queue.add(x);
}
}
}
}
Сложность: O(V + E). В лучшем случае сложность линейная, но в плотных графах сложность может приближаться к квадратичной.


4. Динамическое программирование

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

Задача о рюкзаке
Динамическое программирование эффективно решает задачу о рюкзаке, используя таблицу для хранения промежуточных результатов. Сложность этого алгоритма — O(nW), где n — количество предметов, а W — вместимость рюкзака.
int knapSack(int W, int[] wt, int[] val, int n) {
int[][] K = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
Сложность: O(nW). Например, если n = 10, W = 50, потребуется 500 операций для заполнения таблицы.


#Java #Training #Medium #Algorithm
September 9, 2024