У меня есть набор из точек, которые определены в метрическом пространстве - так что я могу измерить «расстояние» между точками, но больше ничего. Я хочу найти самую центральную точку в этом наборе, которую я определяю как точку с минимальной суммой расстояний до всех остальных точек. Метрические...
Я разместил это на MathUnderflow, но не получил ответов, поэтому решил попробовать здесь, Я читаю старую статью Рабина и Фишера [опубликует ссылку, когда это возможно], где, помимо прочего, доказана двоякая экспоненциальная сложность арифметики Пресбургера. Доказательство основывается на...
Многие классы сложности имеют «полные» проблемы. Существуют ли полные задачи для класса сложности задач, которые можно решить за времени?O(1)O(1)O(1) Сложность состоит в том, что этот класс зависит от модели вычислений; проблема может быть решена за раз в одной разумной модели вычислений, но не в...
Есть несколько примечаний, таких как или и так далее. Мне было интересно, есть ли варианты таких в реальности, как или , или они математически неверны.OOOO(n)O(n)O(n)O(n2)O(n2)O(n^2)O(2n2)O(2n2)O(2n^2)O(logn2)O(logn2)O(\log n^2) Или было бы правильно сказать, что можно улучшить до ? Я не могу и не...