Есть ли проблема решения с временной сложностью Ө (n²)?Существует ли алгоритм решения со сложностью времени Ө (n²)?
Другими словами, я ищу решение проблемы, для которого самое известное решение было доказано, чтобы иметь нижнюю границу N².
Я думал о поиске наибольшего числа в матрице, но проблема в том, что матрица представляет собой вход O (n²), поэтому решение является линейным.
Не нужно быть известной проблемой, достаточно гипотетического.
Существует ли близкая пара?
В любом «трудном» метрическом пространстве, учитывая n точек, делает пару существует на расстоянии меньше, чем r, где r является входного параметра?
Наглядно доказательство:
Учитывая, что r является входным параметром, вы должны искать каждую точку.
В какой-то момент вы вычислили расстояние до любой другой точки, то есть Θ (n).
Для n баллов у вас есть n * Θ (n) = Ө (n²).
Временная сложность: Ө (n²)
Что такое сложные метрические пространства? Неевклидова? –
@ н.м. там их много, а не евклидов. Я хочу сказать, что это не должно быть тривиальным. – gsamaras
Есть ли доступные доказательства? –
Очевидно, что вы не потрудились сделать простой поиск в Интернете. Я просто набрал «проблемы с решением O n^2» в строке поиска и престо, появился следующий PDF: [* «Вычисление проблемы решения проблемы монеты Frobenius в O (n^2)» *] (http: // arxiv .org/pdf/1001.0961.pdf) Проведите некоторое время, прежде чем отправлять вопросы, которые просто вызывают шум. Потребовалось * меньше времени *, чем создание учетной записи и размещение здесь вопроса ... Я уверен, что если вы потратите более 30 секунд на интеллектуальный поиск, вы найдете что-то лучшее. – ray
Поверь мне - я попробовал. И это решение не велико Ө из n^2. Это большой O of n^2/ –
@ray Мне нужно что-то, что вы не можете (и это доказано) быстрее решать .. как найти наибольшее число в массиве большое Ө из n ... У меня уже был вид пузыря, который большой O of n^2. но мне нужно большое Ө n^2. –