Решить задачу с уровнем сложности меньше чем О(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

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

Ясное дело.

Новые блоги и статьи Все статьи Все блоги /
Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .

@korvin_ 4576 / 2775 / 491 Регистрация: 28.04.2012 Сообщений: 8,782
	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