117 записей с тегом "Алгоритмы"

1. Введение​

В этом руководстве мы объясним, как работает алгоритм сортировки на месте.

2. Алгоритмы на месте​

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

Однако на самом деле алгоритм может потребовать небольшого и непостоянного дополнительного пространства для вспомогательных переменных. Сложность этого пространства в большинстве случаев O(log n) , хотя иногда допускается что-то меньшее, чем линейное.

1. Введение​

В этом уроке мы рассмотрим алгоритмы интерполяционного поиска и обсудим их плюсы и минусы. Кроме того, мы реализуем его на Java и поговорим о временной сложности алгоритма.

2. Мотивация​

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

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

1. Обзор​

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

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

В этом уроке мы собираемся, во-первых, пролить свет на эти концепции. Затем мы увидим, как они могут проявить себя в Java.

2. Неконтролируемые алгоритмы​

1. Введение​

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

Мы также поговорим о средней и наихудшей временной сложности каждого алгоритма.

2. Решения​

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

1. Введение​

Задача о рюкзаке — это задача комбинаторной оптимизации, имеющая множество приложений. В этом уроке мы решим эту проблему на Java.

2. Проблема рюкзака​

В задаче о рюкзаке у нас есть набор предметов. Каждый предмет имеет вес и ценность:

1. Введение​

В этой статье мы увидим, как найти k -й наименьший элемент в объединении двух отсортированных массивов.

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

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

2. Что такое K -й наименьший элемент в объединении двух отсортированных массивов?​

1. Введение​

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

Мы предоставим итеративную и рекурсивную реализацию этого алгоритма на Java.

2. Что такое расстояние Левенштейна?​

Расстояние Левенштейна — это мера несходства между двумя строками. Математически, учитывая две строки x и y , расстояние измеряет минимальное количество правок символов, необходимых для преобразования x в y .

1. Обзор​

В этом руководстве мы объясним, как найти средний элемент связанного списка в Java.

В следующих разделах мы представим основные проблемы и покажем различные подходы к их решению.

2. Отслеживание размера​

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

1. Введение​

В этом руководстве мы рассмотрим алгоритм сортировки слиянием и его реализацию в Java .

Сортировка слиянием — один из наиболее эффективных методов сортировки, основанный на парадигме «разделяй и властвуй» .

2. Алгоритм​

Сортировка слиянием — это алгоритм «разделяй и властвуй», в котором мы сначала делим проблему на подзадачи. Когда решения для подзадач готовы, мы объединяем их вместе, чтобы получить окончательное решение проблемы.

1. Введение​

В этом уроке мы узнаем, как объединить два отсортированных массива в один отсортированный массив.

2. Проблема​

Давайте разбираться в проблеме. У нас есть два отсортированных массива, и мы хотели бы объединить их в один.