Описание тега lower-bound

Описание тега Вопросы с тегом
В математике, особенно в теории порядка, нижняя граница подмножества S некоторого частично упорядоченного множества (K, ≤) - это элемент K, который меньше или равен каждому элементу S.
4 ответа

Верхняя и нижняя граница цикла while

В прошлой статье я застрял в вопросе о встроенном программном курсе. Вопрос задает следующее: Let n be the number of iterations of the while loop. Calculate an upper and lower bound on the value of n given that b <= bmax. x=a if x<1 then x=1 e…
21 апр '13 в 21:39
2 ответа

Верхние и нижние оценки в алгоритмах

Я видел несколько статей, описывающих верхнюю границу как наихудший случай и нижнюю границу как наихудший случай. Между тем в некоторых статьях даны объяснения верхней / нижней границы наихудшего случая. В общем, это заставило меня задать три вопрос…
25 май '17 в 11:03
10 ответов

Java-эквивалент C++ equal_range (или lower_bound & upper_bound)

У меня отсортирован список объектов, и я хочу найти первое и последнее вхождение объекта. В C++ я легко могу использовать std::equal_range (или только один lower_bound и один upper_bound). Например: bool mygreater (int i,int j) { return (i>j); } …
24 мар '13 в 20:50
2 ответа

Алгоритмы, верхние / нижние границы и лучший / худший случай

Для алгоритмов, как границы связаны с лучшими / худшими случаями? Является ли худший случай синонимом верхней границы, а лучший - синонимом нижней границы? Или вы можете по крайней мере вывести одно из другого? Или они вообще не связаны?
21 июн '15 в 16:55
1 ответ

Scala типа нижняя ошибка?

case class Level[B](b: B){ def printCovariant[A<:B](a: A): Unit = println(a) def printInvariant(b: B): Unit = println(b) def printContravariant[C>:B](c: C): Unit = println(c) } class First class Second extends First class Third extends Second …
13 апр '16 в 06:54
1 ответ

Есть ли способ найти обратный итератор для первого элемента в std::map меньше заданного ключа?

Я наткнулся на следующий фрагмент кода в C++ (я еще не на C++11): int test(std::map<int, size_t> &threshold, const int value) { std::map<int, size_t>::const_iterator itr = threshold.upper_bound(value); if (threshold.begin() == itr) {…
29 фев '12 в 17:08
2 ответа

Как проверить, есть ли элемент <x в наборе C++

Есть ли элемент, который меньше заданного x в std::set sЕсли нет print, "x меньше, чем любой элемент", если есть, то print "самый большой элемент, который меньше x".Кстати, вы также знаете, что х не входит в набор является: cin &gt;&gt; x; auto it =…
28 авг '18 в 17:11
1 ответ

Могу ли я расширить std::map::lower_bound для поиска по аргументам не-key_type?

Вот иллюстрация моей ситуации. у меня есть std::map и я хочу найти первый pair&lt;key,value&gt; где ключ является любым членом класса эквивалентности ключей. #include &lt;map&gt; struct Category { int foo; int bar; bool operator &lt; (const Category…
05 янв '19 в 12:56
2 ответа

Найти ближайшее значение в векторе

То, что я пытаюсь сделать, это перебирать вектор двойных значений и возвращать векторное положение самого близкого двойника. У меня есть две проблемы с этим. При попытке найти ближайшее двойное значение в векторе, используя lower_bound()Я получаю зн…
05 янв '19 в 20:54
2 ответа

Не удается ограничить метод по правилу нижней границы

Я начал читать о дженериках скалы. Кто может объяснить, почему работает этот код? sealed abstract class Animal class Cat extends Animal class Dog extends Animal class Box[A &gt;: Animal] { def set(a: A): A = ??? } val catBox: Box[Animal] = new Box[A…
28 дек '18 в 13:05
3 ответа

Функция<алгоритма> для нахождения последнего элемента меньше или равного, например lower_bound

Есть ли функция, которая использует бинарный поиск, как lower_bound но что возвращает последний элемент меньше или равный в соответствии с заданным предикатом? lower_bound определяется для: Находит позицию первого элемента в упорядоченном диапазоне,…
03 апр '12 в 08:30
1 ответ

lower_bound по вектору пары после проверки одного значения пары

У меня есть вектор пар vector&lt; pair&lt; string,int&gt; &gt; в C++ и я хочу, чтобы lower_bound для строкового значения, но с дополнительным ограничением, что второе значение пары должно быть меньше или равно заданному значению. В настоящее время я…
09 июн '18 в 07:10
1 ответ

Расчет удерживаемой нижней границы Карпа для коммивояжера (TSP)

В настоящее время я изучаю проблему коммивояжера, и мне было интересно, сможет ли кто-нибудь просто объяснить нижнюю границу удерживаемого карпа. Я смотрел на много бумаг, и я изо всех сил пытаюсь понять это. Если бы кто-то мог просто объяснить это,…
10 апр '14 в 10:36
1 ответ

Использование нижней границы с вектором указателей объектов

У меня есть эта структура данных: class Person { public: string email, name, surname }; class Bus { vector&lt;Person *&gt; sortedbyemail; vector&lt;Person *&gt; sortedbyname; }; Теперь я хочу добавить указатели в правильную позицию, поэтому мне не п…
30 мар '18 в 22:04
9 ответов

Обоснование для std::lower_bound и std::upper_bound?

STL предоставляет бинарные функции поиска std::lower_bound и std::upper_bound, но я не использую их, потому что не могу вспомнить, что они делают, потому что их контракты кажутся мне совершенно загадочными. Просто взглянув на имена, я бы предположил…
08 май '14 в 23:47
1 ответ

Алгоритм двоичного поиска C++ для работы как lower_bound

У меня есть еще один вопрос после моего предыдущего - Я создаю версию lower_bound с чем-то вроде бинарного поиска. С BinarySearch Функция Я нахожу место для вставки нового элемента и с помощью цикла for я перемещаю остальную часть массива и вставляю…
14 апр '15 в 18:36
2 ответа

Структура как приоритетная очередь, но с чем-то вроде нижней границы

Я хочу, чтобы структура сохраняла (например) числа, в которые я могу вставлять и удалять элементы, моя структура всегда сортируется (как очередь с приоритетами), НО с возможностью узнать, где находится данное число, и каждую операцию в логарифмическ…
18 ноя '17 в 20:42
1 ответ

Нахождение нижней и верхней границы сложности

Я хочу найти нижнюю и верхнюю границу сложности этого алгоритма 1: for all i=1 to n*n do 2: for all j=i to 2*i do 3: output “hello world” 4: end for 5: end for Записав это как суммирование и упростив f(n) = 0.5*n^4 + 1.5*n^2 Похоже, что верхняя гран…
02 май '18 в 15:00
0 ответов

Нижние и верхние границы в питоне

Я не знаю, находится ли этот вопрос в правильном месте или нет, если нет, пожалуйста, скажите мне. Итак, я использую Python, и я должен оптимизировать функцию стоимости, которая имеет два ограничения. Эта функция стоимости не увеличивается по отноше…
23 апр '16 в 12:27
3 ответа

Странное поведение вывода типа в функции с верхней границей

Столкнулся с этим странным поведением, когда изменил верхнюю границу в реализации, но забыл изменить ее в интерфейсе. Я думаю, что последнее утверждение не должно компилироваться, но оно делает и возвращает неожиданный результат. trait SuperBase tra…
12 ноя '15 в 17:44