Big O Notation: Сложность алгоритмов

🔵 O(1) — Константное время
Константное время выполнения означает, что время выполнения операции не зависит от размера входных данных. Это как мгновенный доступ к элементу массива по индексу. Независимо от того, сколько данных в массиве, операция займёт одно и то же время.

🔵 O(n) — Линейное время
Линейная сложность указывает на то, что время выполнения алгоритма растёт пропорционально количеству элементов. Поиск элемента в LinkedList — классический пример. Чтобы найти нужный элемент, вам придётся пройти весь список, начиная с головы, что займёт линейное время, если искомый элемент находится в конце.

🔵 O(log n) — Логарифмическое время
В логарифмических алгоритмах задача сокращается на каждом шаге вдвое. Пример — бинарный поиск в отсортированном массиве. На каждом шаге вы делите массив пополам, и продолжаете поиск в нужной половине. Это значительно быстрее, чем линейный поиск.

🔵 O(n^2) — Квадратичное время
В алгоритмах с квадратичной сложностью каждый элемент сравнивается с каждым другим. Примером является сортировка пузырьком (Bubble Sort), где алгоритм многократно сравнивает и обменивает элементы местами, что приводит к квадратичному времени выполнения при увеличении числа элементов.

🔵 O(n^3) — Кубическое время
Кубическая сложность встречается в задачах с тройными вложенными циклами. Пример — умножение матриц, где каждый элемент одной матрицы должен быть умножен на каждый элемент другой, что приводит к тройным вложенным операциям.

🔵 O(n log n) — Линейно-логарифмическое время
Линейно-логарифмическая сложность характерна для более продвинутых алгоритмов сортировки, таких как быстрая сортировка (QuickSort) или сортировка слиянием (MergeSort). Эти алгоритмы делят массив на части и сортируют их, что делает их более эффективными по сравнению с квадратичными.

🔵 O(2^n) — Экспоненциальное время
Экспоненциальная сложность наблюдается в рекурсивных алгоритмах, таких как вычисление чисел Фибоначчи без мемоизации. На каждом шаге создаётся две новые ветви вычислений, что приводит к экспоненциальному росту времени выполнения с увеличением входных данных.

🔵 O(n!) — Факториальное время
Факториальная сложность возникает в задачах, связанных с вычислением всех возможных перестановок или комбинаций. Например, задача генерации всех перестановок строки: с увеличением длины строки число возможных комбинаций возрастает факториально.

🔵 O(√n) — Время квадратного корня
Этот тип сложности встречается, например, в алгоритмах поиска делителей числа или проверки на простоту. Например, чтобы проверить, является ли число простым, достаточно проверить делители до его квадратного корня, что сокращает количество операций по сравнению с линейным подходом.

@javalib #java

👩‍💻 Java — один из самых востребованных языков, но не каждый разработчик умеет использовать его возможности по максимуму.

На курсе «Java Developer. Professional» вы научитесь создавать современные Java-приложения, освоите Spring WebFlux и Kafka, а также разберётесь в работе JVM изнутри.

Вас ждёт практическая работа с кодом, детальные разборы, ревью от экспертов и подходы, позволяющие писать эффективный и чистый код.

Начните свой путь к уровню Middle+! Используйте Java на 100%.

➡️ Пройти вступительный тест курса: https://vk.cc/cEUHvj

🎁 Только в "Черную пятницу", скидки на курс до 15%! Подробности у менеджеров.

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

💯 Хватит ждать вечность, пока выполняются тесты!

➡️ Многопоточность в Java — это ключ к ускорению процессов.
Хотите, чтобы тесты запускались параллельно и быстро? Приходите на открытый урок 20 ноября в 20:00 мск и узнайте, как использовать многопоточность и futures для суперэффективной автоматизации.

✔️ Мы покажем, как работать с потоками и futures в Java, а также обсудим параллельные циклы и их применение в тестировании. Научитесь ускорять автотесты, оптимизировать процессы и прокачивать навыки, востребованные на рынке!

🎙️ Спикер Павел Балахонов — ведущий инженер по автоматизированному тестированию на проекте VK Private Cloud Solutions, опытный ментор и преподаватель.

⤵️ Хотите стать экспертом в автоматизации тестирования на Java? Запишитесь на урок и получите скидку на участие в курсе «Java QA Engineer. Professional»: https://vk.cc/cEUxSl

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

🖥 JDK, JRE и JVM

▪️ JDK (Java Development Kit) — это набор инструментов для разработки приложений на Java. Включает компилятор, библиотеки и утилиты, необходимые для написания и сборки кода.

▪️ JRE (Java Runtime Environment) — среда выполнения, которая позволяет запускать Java-приложения. Включает в себя JVM и стандартные библиотеки, но без инструментов разработки.

▪️ JVM (Java Virtual Machine) — виртуальная машина, которая исполняет байт-код, сгенерированный при компиляции. Именно JVM делает Java переносимой, так как позволяет запускать программы на разных платформах.

@javalib #java

⚡️ Как избавиться от задержек и сделать систему быстрее

1️⃣ Кэширование

Временное хранение часто используемых данных в памяти для сокращения времени доступа.

▪️ Чем полезно:
- Получение данных из кэша (например, Redis, Memcached) гораздо быстрее, чем запросы к базе данных.
- Кэширование статических ресурсов (изображения, CSS, JS) снижает необходимость многократного запроса их с исходного сервера.

2️⃣ Распределение нагрузки

Распределение входящего сетевого трафика между несколькими серверами для предотвращения перегрузки одного сервера.

▪️ Чем полезно:
- Балансировка нагрузки предотвращает перегрузку одного сервера, что может замедлить отклик.
- Обеспечивает отказоустойчивость, гарантируя обработку запросов даже при выходе некоторых серверов из строя.

3️⃣ Асинхронная обработка

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

▪️ Чем полезно:
- Пользователям не нужно ждать завершения длительных задач (например, отправки электронной почты или обработки изображений).

4️⃣ Разделение данных (шардирование)

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

▪️ Чем полезно:
- Запросы могут выполняться параллельно на нескольких шардах, сокращая время получения данных.
- Распределение нагрузки предотвращает перегрузку одного экземпляра базы данных.

5️⃣ Сети доставки контента (CDA)

Распределенные сети серверов, которые доставляют веб-контент на основе географического расположения пользователя.

▪️ Чем полезно:
- Контент предоставляется с серверов, находящихся ближе к пользователю, сокращая физическое расстояние, которое данные должны преодолеть.
- Кэширует статический и динамический контент для ускорения его доставки.

6️⃣ Оптимизация баз данных

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

▪️ Чем полезно:
- Ускоряет получение данных, позволяя базе данных находить записи без сканирования всех таблиц.

7️⃣ Минимизация сетевых переходов

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

▪️ Чем полезно:
- Каждый сетевой переход добавляет задержку; их минимизация ускоряет передачу данных.

8️⃣ Параллельная и конкурентная обработка

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

▪️ Чем полезно:
- Параллельное выполнение задач позволяет обрабатывать данные быстрее за счёт разделения работы на несколько потоков.
- Более эффективное использование ресурсов процессора, что снижает задержки при выполнении сложных операций.

9️⃣ Предварительная и предсказательная загрузка

Предугадывание будущих запросов данных и их предварительная загрузка.

▪️ Чем полезно:
- Данные уже доступны, когда они запрашиваются, устраняя задержки при получении.
- Особенно эффективно в приложениях с предсказуемыми шаблонами доступа.

@javalib #java