Решить задачу с уровнем сложности меньше чем О(n^2)

@matuf · Регистрация: 20.02.2021

Студворк — интернет-сервис помощи студентам

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

Java
1
2
3
4
5
6
7
public class SpravneZavazia {
 
        public static boolean obsahujeVyberSHmotnostou(int[] zavazia, int h) {
                return true;
        }
 
}

Нужно решить данное задание лучшем чем o(n^2)

@korvin_ · 06.03.2021, 18:28

Arsegg, второе — найти такие две гири, сумма весов которых равна h, это вполне стандартная алгоритмическая задача. Формулировка немного кривая. Разве что ТС это опровергнет, но тогда это будет очень странно.

@Arsegg · 06.03.2021, 18:59

korvin_, правильно ли я понял, что вы хотели реализовать данный алгоритм: Given a sorted array and a number x, find the pair in array whose sum is closest to x? Т. е. найти такую пару весов, сумма которой стремится к h, и если данная сумма равна h возвращать true?

Добавлено через 8 минут
Изначально, я не обратил внимания на то, что массив был изначально отсортирован, и поэтому смотрел на решение проблемы через хеширование. Если не задействовать доп. память (хеш-таблицу), можно перестроить входной массив (неотсортированный) в хеш-таблицу с открытой адресацией (разрешение коллизий можно взять любое: линейное, квадратичное, кукушки и т. п.) за один проход, а за второй - уже, собственно, искать пару. Время работы будет линейное без доп. памяти.

@Tavashi · 06.03.2021, 20:10

Сообщение от Arsegg

товарищи, ну вы что? vcrop уже решил за линию.

Можно и без HashSet:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        public static boolean obsahujeVyberSHmotnostou(int[] zavazia, int h) {
            int lowest = 0;
            int highest = zavazia.length - 1;
            
            while (lowest < highest) {
                System.out.println(zavazia[lowest] + " " + zavazia[highest]);
                if (zavazia[lowest] + zavazia[highest] == h)
                    return true;
                
                if (zavazia[lowest] + zavazia[highest] > h)
                    highest--;
                else 
                    lowest++;
            }
            return false;
 
        }

Сообщение от Arsegg

Если в бакете элементов меньше 8, то сложность линейная

А если нет?

Добавлено через 3 минуты

Сообщение от korvin_

Разве что ТС это опровергнет, но тогда это будет очень странно.

Маловероятно, что опровергнет и на этот случай решение уже есть.

@Arsegg · 06.03.2021, 21:18

Сообщение от Tavashi

А если нет?

Если нет, то связный список перестраивается в красно-черное дерево. А там поиск идет за логарифм.

@Tavashi · 06.03.2021, 23:21

Сообщение от Arsegg

поиск идет за логарифм.

Что и увеличит время для редкого случая.

@Arsegg · 07.03.2021, 12:07

Сообщение от Tavashi

Что и увеличит время для редкого случая.

Чтобы не увеличивало: пишешь perfect hash function и получаешь гарантированную константу.

@Tavashi · 07.03.2021, 17:00

Сообщение от Arsegg

perfect hash function

Такой не существует.

@Arsegg · 07.03.2021, 18:51

Не по теме:

Сообщение от Tavashi

Такой не существует.

Я бы так не утверждал))

Добавлено через 4 минуты

Не по теме:

Tavashi, кури.

@Tavashi · 07.03.2021, 20:10

Arsegg, perfect hash function и minimal perfect hashing не одно и то же. Автор статьи как раз об этом пишет.

@Arsegg · 07.03.2021, 21:21

Сообщение от Tavashi

perfect hash function и minimal perfect hashing не одно и то же.

Упрлс? Учи мат. часть: Minimal perfect hash function!

A minimal perfect hash function is a perfect hash function...

@Tavashi · 08.03.2021, 01:36

Сообщение от Arsegg

A minimal perfect hash function is a perfect hash function..

Есть описание дальше одной строчки:

Then F is a minimal perfect hash function if and only if F(j) = F(k) implies j = k (injectivity) and there exists an integer a such that the range of F is a..a + |S| − 1.

Другими словами, это то о чем пишет автор статьи:

Perfect hashing is a technique for building a hash table with no collisions. It is only possible to build one when we know all of the keys in advance.

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

A perfect hash function (PHF) h : S → [0, m − 1] for a key set S ⊆ U of size n, where m ≥ n and U is a key universe, is an injective function that maps the keys of S to unique values. A minimal perfect hash function (MPHF) is a PHF with m = n, the smallest possible range.

@Arsegg · 08.03.2021, 14:26

Сообщение от Tavashi

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

Ясное дело.

Новые блоги и статьи Все статьи Все блоги /
Сезонность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .

@korvin_ 4576 / 2775 / 491 Регистрация: 28.04.2012 Сообщений: 8,781
	06.03.2021, 18:28
	Arsegg, второе — найти такие две гири, сумма весов которых равна h, это вполне стандартная алгоритмическая задача. Формулировка немного кривая. Разве что ТС это опровергнет, но тогда это будет очень странно. 1

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	06.03.2021, 18:59
	korvin_, правильно ли я понял, что вы хотели реализовать данный алгоритм: Given a sorted array and a number x, find the pair in array whose sum is closest to x? Т. е. найти такую пару весов, сумма которой стремится к `h`, и если данная сумма равна `h` возвращать `true`? Добавлено через 8 минут Изначально, я не обратил внимания на то, что массив был изначально отсортирован, и поэтому смотрел на решение проблемы через хеширование. Если не задействовать доп. память (хеш-таблицу), можно перестроить входной массив (неотсортированный) в хеш-таблицу с открытой адресацией (разрешение коллизий можно взять любое: линейное, квадратичное, кукушки и т. п.) за один проход, а за второй - уже, собственно, искать пару. Время работы будет линейное без доп. памяти. 0

@Tavashi 1172 / 762 / 194 Регистрация: 21.05.2016 Сообщений: 1,858
	07.03.2021, 20:10
	Arsegg, perfect hash function и minimal perfect hashing не одно и то же. Автор статьи как раз об этом пишет. 0