Есть ли O (1 / n) алгоритмы?

335

Есть ли O (1 / n) алгоритмы?

Или что-нибудь еще, что меньше, чем O (1)?

Peter Mortensen
источник
В большинстве вопросов предполагается, что вы имеете в виду «Существуют ли алгоритмы с временной сложностью O (1 / n)?» Должны ли мы предположить, что это так? Big-O (и Big-Theta и т. Д.) Описывают функции, а не алгоритмы. (Я не знаю никакой эквивалентности между функциями и алгоритмами.)
jyoungdev
4
Это общепринятое определение «алгоритма O (X)» в компьютерной науке: алгоритм, сложность которого по времени равна O (X) (для некоторого выражения X).
Дэвид З,
2
Я слышал такую ​​границу в случае алгоритма очереди с эффективным приоритетом ввода / вывода, использующего дерево буферов. В дереве буферов каждая операция принимает O (1 / B) операций ввода-вывода; где B - размер блока. И общее количество операций ввода- вывода для n операций составляет O (n / B.log (base M / B) (n / B)), где log-часть - высота дерева буферов.
Ошибка кода
Существует множество алгоритмов с вероятностью ошибки O (1 / n). Например, фильтр Блума с O (n log n) сегментами.
Томас Але
Вы не можете отложить яйцо быстрее, добавив кур.
Вик

Ответы:

310

Этот вопрос не так глуп, как может показаться. По крайней мере, теоретически, что-то вроде O (1 / n ) совершенно разумно, когда мы берем математическое определение обозначения Big O :

Теперь вы можете легко заменить g ( x ) на 1 / x ... очевидно, что приведенное выше определение все еще верно для некоторого f .

Для оценки асимптотического роста во время выполнения это менее жизнеспособно ... значимый алгоритм не может работать быстрее по мере роста входных данных. Конечно, вы можете построить произвольный алгоритм для выполнения этого, например, следующий:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

Ясно, что эта функция тратит меньше времени по мере увеличения размера ввода… по крайней мере, до некоторого предела, навязанного аппаратными средствами (точность чисел, минимум времени, которое sleepможет ждать, время для обработки аргументов и т. Д.): Тогда этот предел будет постоянная нижняя граница, так что фактически вышеприведенная функция все еще имеет время выполнения O (1).

Но это на самом деле реальных алгоритмов , где среда выполнения может уменьшаться (по крайней мере , частично) , когда увеличивается размер входного. Обратите внимание, что эти алгоритмы не будут демонстрировать поведение во время выполнения ниже O (1). Тем не менее, они интересные. Например, возьмем очень простой алгоритм поиска текста Хорспула . Здесь ожидаемое время выполнения будет уменьшаться по мере увеличения длины шаблона поиска (но увеличение длины стога сена еще раз увеличит время выполнения).

Конрад Рудольф
источник
22
«Применяется аппаратными средствами» также относится к машине Тьюринга. В случае O (1 / n) всегда будет входной размер, для которого алгоритм не должен выполнять какую-либо операцию. И поэтому я думаю, что O (1 / n) временной сложности действительно невозможно достичь.
Роланд Эвальд
28
Мердад, ты не понимаешь. Обозначение O является чем-то вроде предела (технически lim sup) при n -> ∞. Время выполнения алгоритма / программы - это количество шагов на некоторой машине, и поэтому оно дискретно - существует ненулевая нижняя граница времени, которое может занять алгоритм («один шаг»). Это является возможным , что ДО некоторых конечной N программы принимает ряд шагов убывающих с п, но единственный способом алгоритм может быть O (1 / п), или на самом деле о (1), если это требуется время 0 для всех достаточно большое п - что невозможно.
ShreevatsaR
28
Мы не согласны с тем, что O (1 / n) функции (в математическом смысле) существуют. Очевидно, что они делают. Но вычисления по своей природе дискретны. То, что имеет нижнюю границу, например, время выполнения программы - либо на архитектуре фон Неймана, либо на чисто абстрактной машине Тьюринга - не может быть O (1 / n). Эквивалентно, то, что является O (1 / n), не может иметь нижнюю границу. (Ваша функция «сна» должна быть вызвана, или переменная «список» должна быть проверена - или входная лента должна быть проверена на машине Тьюринга. Таким образом, время, которое потребуется, изменится на n как некоторое ε + 1 / n, который не является O (1 / n))
ShreevatsaR
16
Если T (0) = ∞, оно не останавливается. Не существует такой вещи, как «T (0) = ∞, но она все еще останавливается». Кроме того, даже если вы работаете в R∪ {∞} и определяете T (0) = ∞ и T (n + 1) = T (n) / 2, то T (n) = ∞ для всех n. Позвольте мне повторить: если дискретная функция равна O (1 / n), то для всех достаточно больших n она равна 0. [Доказательство: T (n) = O (1 / n) означает, что существует постоянная c такая, что для n> N0 T (n) <c (1 / n), что означает, что для любого n> max (N0,1 / c), T (n) <1, что означает T (n) = 0.] ни одна машина, реальный или абстрактный, не может принимать 0 раз: он должен смотреть на входе. Ну, кроме машины, которая никогда ничего не делает, и для которой T (n) = 0 для всех n.
ShreevatsaR
43
Вам должен понравиться любой ответ, который начинается «Этот вопрос не так глуп, как может показаться».
Телемах
138

Да.

Существует точно один алгоритм с временем выполнения O (1 / n), «пустой» алгоритм.

Если алгоритм равен O (1 / n), это означает, что он выполняется асимптотически за меньшее количество шагов, чем алгоритм, состоящий из одной инструкции. Если он выполняется менее чем за один шаг для всех n> n0, он должен состоять из абсолютно никаких инструкций для этих n. Поскольку проверка 'if n> n0' стоит как минимум 1 инструкцию, она не должна содержать команду для всех n.

Подводя итог: единственный алгоритм , который является O (1 / N) является пустой алгоритм, состоящий из не инструкции.

Тобиас
источник
2
Итак, если бы кто-то спросил, какова временная сложность пустого алгоритма, вы бы ответили O (1 / n) ??? Я почему-то сомневаюсь в этом.
phkahler
24
Это единственный правильный ответ в этой теме, и (несмотря на мое возражение) он набрал ноль голосов. Таков StackOverflow, где «правильные» ответы оцениваются выше, чем правильные.
ShreevatsaR
5
Нет, его рейтинг 0, потому что это неверно. Выражение большого значения Oh по отношению к N, когда оно не зависит от N, неверно. Во-вторых, запуск любой программы, даже той, которая только что существует, занимает по меньшей мере постоянное время O (1). Даже если бы это было не так, это было бы O (0), а не O (1 / n).
kenj0418
32
Любая функция, которая является O (0), также является O (1 / n), а также O (n), также O (n ^ 2), также O (2 ^ n). Вздох, никто не понимает простых определений? O () - верхняя граница.
ShreevatsaR
16
@ kenj0418 Вам удалось ошибиться в каждом предложении. «Неверно выражать значение« большой О »по отношению к N, когда оно не зависит от N». Постоянная функция - совершенно бездарная функция. «Во-вторых, запуск любой программы, даже той, которая только что существует, занимает по меньшей мере постоянное количество времени, O (1)». Определение сложности ничего не говорит о действительном запуске каких-либо программ. msgstr "это будет O (0), а не O (1 / n)". Смотрите комментарий @ ShreevatsaR.
Алексей Романов
25

острый зуб правильный, O (1) - наилучшая возможная производительность. Тем не менее, это не означает быстрое решение, просто решение с фиксированным временем.

Интересный вариант, и, возможно, то, что действительно предлагается, заключается в том, какие проблемы становятся легче по мере роста населения. Я могу думать о 1, хотя надуманный и насмешливый ответ:

Есть ли у двух людей в наборе один и тот же день рождения? Когда n превышает 365, верните true. Хотя для менее чем 365 это O (n ln n). Возможно, не очень хороший ответ, так как проблема не становится легче, а просто становится O (1) для n> 365.

Adrian
источник
7
366. Не забывай о високосных годах!
Ник Джонсон
1
Ты прав. Как и компьютеры, я иногда подвержен ошибкам округления :-)
Адриан
10
+1. Существует ряд NP-полных задач, которые претерпевают «фазовый переход» при увеличении n, то есть они быстро становятся намного проще или намного сложнее, когда вы превышаете определенное пороговое значение n. Одним из примеров является проблема разбиения чисел: учитывая набор из n неотрицательных целых чисел, разделите их на две части так, чтобы сумма каждой части была равна. Это значительно упрощается при определенном пороговом значении n.
j_random_hacker
23

Это невозможно. Определение Big-O не больше, чем неравенство:

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

Таким образом, B (n) на самом деле является максимальным значением, поэтому, если оно уменьшается при увеличении n, оценка не изменится.

Sharptooth
источник
42
Я подозреваю, что этот ответ является «правильным», но, к сожалению, мне не хватает интеллекта, чтобы понять его.
свободное пространство
12
AFAIK это условие не обязательно должно быть истинным для всех n, но для всех n> n_0 (т. Е. Только тогда, когда размер входа достигает определенного порога).
Роланд Эвальд
30
Я не вижу, как определение (даже исправленное) противоречит вопросу ОП. Определение справедливо для совершенно произвольных функций! 1 / n - вполне разумная функция для B, и фактически ваше уравнение не противоречит этому (просто посчитайте). Так что нет, несмотря на большое согласие, этот ответ на самом деле неверен . Сожалею.
Конрад Рудольф
10
Неправильно! Я не люблю понизить голосование, но вы заявляете, что это невозможно, когда нет четкого консенсуса. На практике вы правы, если вы конструируете функцию с временем выполнения 1 / n (просто), она в конечном итоге достигнет минимального времени, фактически превратив его в алгоритм O (1) при реализации. Однако ничто не мешает алгоритму быть O (1 / n) на бумаге.
Джерико
3
@Jason: Да, теперь, когда вы это говорите ... :) @jheriko: Временная сложность O (1 / n) не работает на бумаге, ИМХО. Мы характеризуем функцию роста f (входной размер) = #ops для машины Тьюринга. Если после x шагов он останавливается на входе длины n = 1, тогда я выберу размер ввода n >> x, то есть достаточно большой, чтобы, если алгоритм действительно находится в O (1 / n), ни одна операция не выполнялась сделано. Как машина Тьюринга должна заметить это (ей нельзя читать с ленты один раз)?
Роланд Эвальд
16

Из моего предыдущего изучения больших обозначений O, даже если вам нужен 1 шаг (например, проверка переменной, выполнение присваивания), то есть O (1).

Обратите внимание, что O (1) совпадает с O (6), потому что «константа» не имеет значения. Вот почему мы говорим, что O (n) совпадает с O (3n).

Таким образом, если вам нужен хотя бы один шаг, это O (1) ... и, поскольку вашей программе требуется по крайней мере 1 шаг, минимум алгоритма может быть равен O (1). Если мы не сделаем этого, то это O (0), я думаю? Если мы вообще что-то делаем, то это O (1), и это минимум, на который можно пойти.

(Если мы решим не делать этого, то это может стать вопросом дзен или дао ... в области программирования O (1) по-прежнему является минимальным).

Или как насчет этого:

программист : босс, я нашел способ сделать это за O (1) раз!
босс : нет необходимости делать это, мы обанкротились сегодня утром.
программист : о, тогда он становится O (0).

動靜 能量
источник
Ваша шутка напомнила мне кое-что из Дао Программирования: canonical.org/~kragen/tao-of-programming.html#book8 (8.3)
kenj0418
Алгоритм, состоящий из нулевых шагов, равен O (0). Это очень ленивый алгоритм.
Вскоре
8

Нет, это невозможно:

Поскольку n стремится к бесконечности в 1 / n, мы в конечном итоге достигаем 1 / (inf), что фактически равно 0.

Таким образом, биг-о-классом задачи будет O (0) с массивным n, но ближе к постоянному времени с низким n. Это не имеет смысла, так как единственное, что можно сделать быстрее, чем постоянное время, это:

void nothing() {};

И даже это спорно!

Как только вы выполняете команду, вы попадаете как минимум в O (1), поэтому нет, у нас не может быть класса big-oh O (1 / n)!

Эд Джеймс
источник
7

Как насчет того, чтобы вообще не запускать функцию (NOOP)? или используя фиксированное значение. Это считается?

косяк
источник
16
Это все еще O (1) время выполнения.
Конрад Рудольф
2
Да, это все еще O (1). Я не понимаю, как кто-то может это понять, и все же в другом ответе утверждают, что возможно нечто меньшее, чем NO-OP.
ShreevatsaR
4
ShreevatsaR: нет абсолютно никакого противоречия. Похоже, вы не понимаете, что большие обозначения O не имеют никакого отношения к времени, проведенному в функции - скорее, они описывают, как это время изменяется с изменением ввода (выше определенного значения). Смотрите другую ветку комментариев для более.
Конрад Рудольф
Я прекрасно это понимаю, спасибо. Суть - как я уже несколько раз говорил в другом потоке - в том, что если время уменьшается с входом со скоростью O (1 / n), то оно должно в конечном итоге уменьшиться ниже времени, затрачиваемого NOOP. Это показывает, что ни один алгоритм не может быть O (1 / n) асимптотически, хотя, конечно, его время выполнения может уменьшиться до предела.
ShreevatsaR
1
Да ... как я сказал в другом месте, любой алгоритм, который является O (1 / n), должен также занять нулевое время для всех входных данных, поэтому в зависимости от того, считаете ли вы, что нулевой алгоритм занимает 0 времени или нет, существует O (1). / п) алгоритм. Таким образом, если вы рассматриваете NOOP как O (1), то нет O (1 / n) алгоритмов.
ShreevatsaR
7

Я часто использую O (1 / n) для описания вероятностей, которые становятся меньше по мере увеличения входных данных - например, вероятность того, что честная монета выпадет в хвост на log2 (n) бросках, равна O (1 / n).

Дейв
источник
6
Это не то, что большой О, хотя. Вы не можете просто переопределить это, чтобы ответить на вопрос.
Zifre
11
Это не переопределение, это именно определение большого О.
ShreevatsaR
10
Я по профессии теоретик-информатик. Речь идет об асимптотическом порядке функции.
Дейв
4
Большой O является свойством произвольной вещественной функции. Сложность времени - это только одно из возможных применений. Пространственная сложность (объем рабочей памяти, используемый алгоритмом) - это другое. То, что вопрос касается алгоритмов O (1 / n) , подразумевает, что это один из них (если только нет другого, применимого к алгоритмам, о которых я не знаю). Другие приложения включают в себя порядки роста населения, например, в жизни Конвея. См. Также en.wikipedia.org/wiki/Big_O_notation
Стюарт
5
@Dave: Вопрос не в том, существуют ли функции O (1 / n), которые, очевидно, существуют. Скорее, это было то, существуют ли O (1 / n) алгоритмы, которые (за возможным исключением нулевой функции) не могут существовать
Casebash
6

O (1) просто означает «постоянное время».

Когда вы добавляете ранний выход в цикл [1], вы (в нотации big-O) превращаете алгоритм O (1) в O (n), но делаете его быстрее.

Хитрость в том, что алгоритм с постоянным временем является лучшим, а линейный лучше, чем экспоненциальный, но при малых значениях n экспоненциальный алгоритм может быть на самом деле быстрее.

1: Предполагая длину статического списка для этого примера

LapTop006
источник
6

Для тех, кто читает этот вопрос и хочет понять, о чем идет речь, это может помочь:

|    |constant |logarithmic |linear|  N-log-N |quadratic|  cubic  |  exponential  |
|  n |  O(1)   | O(log n)   | O(n) |O(n log n)|  O(n^2) |  O(n^3) |     O(2^n)    |
|  1 |       1 |          1 |     1|         1|        1|       1 |             2 |
|  2 |       1 |          1 |     2|         2|        4|       8 |             4 |
|  4 |       1 |          2 |     4|         8|       16|      64 |            16 |
|  8 |       1 |          3 |     8|        24|       64|     512 |           256 |
| 16 |       1 |          4 |    16|        64|      256|   4,096 |         65536 |
| 32 |       1 |          5 |    32|       160|    1,024|  32,768 | 4,294,967,296 |
| 64 |       1 |          6 |    64|       384|    4,069| 262,144 |   1.8 x 10^19 |
Крейг О'Коннор
источник
5

Я считаю, что квантовые алгоритмы могут делать несколько вычислений "одновременно" посредством суперпозиции ...

Я сомневаюсь, что это полезный ответ.

Джефф Фрикадель Ян
источник
Это все равно будет постоянное время, т.е. O (1), что означает, что для данных размера n требуется столько же времени, сколько для данных размера 1.
свободное пространство
2
Но что, если проблема была в бледном эле? (ах. ха. ха.)
Джефф Фрикадель Ян
7
Это было бы супер положение , чтобы быть в.
Daniel Earwicker
1
Квантовые алгоритмы могут выполнять несколько вычислений, но вы можете получить только результат одного вычисления, и вы не можете выбрать, какой результат получить. К счастью, вы также можете выполнять операции с квантовым регистром в целом (например, QFT), так что вы с большей вероятностью найдете что-нибудь :)
Gracenotes
2
это, возможно, бесполезно, но у него есть преимущество в том, чтобы быть правдой, что ставит его выше некоторых наиболее высоко
оцененных
4

у многих людей был правильный ответ (Нет). Вот еще один способ доказать это: для того, чтобы иметь функцию, вы должны вызвать функцию и вернуть ответ. Это занимает определенное постоянное количество времени. ДАЖЕ ЕСЛИ для остальной обработки потребовалось меньше времени для больших входных данных, то распечатка ответа (который мы можем считать единичным битом) занимает, по крайней мере, постоянное время.

Брайан Постов
источник
2

Если решение существует, оно может быть подготовлено и доступно в постоянное время = немедленно. Например, используя структуру данных LIFO, если вы знаете, что сортировочный запрос для обратного порядка. Затем данные уже отсортированы, учитывая, что была выбрана соответствующая модель (LIFO).

Ларссон
источник
2

Какие проблемы становятся легче по мере роста населения? Одним из ответов является нечто вроде bittorrent, где скорость загрузки является обратной функцией числа узлов. В отличие от автомобиля, который замедляется при загрузке, сеть обмена файлами, такая как bittorrent, ускоряет подключение большего количества узлов.

Никлас Р.
источник
Да, но число узлов bittorrent больше похоже на количество процессоров в параллельном компьютере. В этом случае буквой «N» будет размер файла, который нужно загрузить. Точно так же, как вы могли бы найти элемент в несортированном массиве длины N в постоянном времени, если у вас было N компьютеров, вы можете загрузить файл размера N в постоянном времени, если у вас было N компьютеров, пытающихся отправить вам данные.
Кибби
2

Вы не можете опуститься ниже O (1), однако O (k), где k меньше N, возможно. Мы назвали их сублинейными алгоритмами времени . В некоторых задачах алгоритм сублинейного времени может дать только приблизительные решения конкретной задачи. Однако иногда приблизительные решения просто хороши, возможно, из-за того, что набор данных слишком велик или что он слишком дорог для вычислений, чтобы вычислить все.

оборота Хао Вуй Лим
источник
1
Не уверен, что понимаю. Log (N) меньше N. Означает ли это, что Log (N) является сублинейным алгоритмом? И многие алгоритмы Log (N) существуют. Одним из таких примеров является поиск значения в двоичном дереве. Однако они по-прежнему отличаются от 1 / N, поскольку Log (N) всегда увеличивается, а 1 / n - убывающая функция.
Кибби
Если посмотреть на определение, сублинейный алгоритм времени - это любой алгоритм, время которого растет медленнее, чем размер N. Так что он включает алгоритм логарифмического времени, который является Log (N).
Хао Вуй Лим
2
Э-э, алгоритмы сублинейного времени могут дать точные ответы, например, бинарный поиск в упорядоченном массиве на машине RAM.
А. Рекс
@A. Рекс: Хао Вуй Лим сказал: «В некоторых проблемах».
LarsH
1

Как насчет этого:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

с ростом размера списка ожидаемое время выполнения программы уменьшается.

Shalmanese
источник
я думаю, что вы не понимаете значения O (n)
Маркус Лозберг
Но не со списком, а с массивом или хэшем, где constainsO (1)
vava
Хорошо, случайная функция может рассматриваться как ленивый массив, так что вы в основном ищите каждый элемент в «ленивом случайном списке» и проверяете, содержится ли он во входном списке. Я думаю, что это хуже, чем линейный, а не лучше.
Хазен
У него есть смысл, если вы заметили, что int имеет ограниченный набор значений. Поэтому, когда l будет содержать 2 <sup> 64 </ sup> значения, оно будет происходить мгновенно. Что делает его хуже, чем O (1) в любом случае :)
vava
1

O (1 / n) не меньше, чем O (1), это означает, что чем больше у вас данных, тем быстрее работает алгоритм. Скажем, вы получаете массив и всегда заполняете его до 10 100 элементов, если в нем меньше, и ничего не делаете, если есть больше. Это, конечно, не O (1 / n), а что-то вроде O (-n) :) Слишком плохая запись O-big не допускает отрицательных значений.

вава
источник
1
«O (1 / n) не меньше, чем O (1)» - если функция f есть O (1 / n), это также O (1). И big-oh очень похоже на отношение «меньше чем»: оно рефлексивно, оно транзитивно, и если мы имеем симметрию между f и g, то оба эквивалентны, где big-theta - наше отношение эквивалентности. «Реальные» упорядоченные отношения ISTR, требующие a <= b и b <= a, подразумевают a = b, и википедия netcraft ^ W подтверждает это. Таким образом, в некотором смысле справедливо сказать, что действительно O (1 / n) «меньше» O (1).
Йонас Кёлкер
1

Как уже указывалось, кроме возможного исключения нулевой функции, не может быть никаких O(1/n)функций, так как время, которое потребуется, должно приблизиться к 0.

Конечно, есть некоторые алгоритмы, подобные определенным Конрадом, которые кажутся такими, что их должно быть меньше, чем O(1)в каком-то смысле.

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

Если вы хотите исследовать эти алгоритмы, вы должны либо определить собственное асимптотическое измерение, либо свое собственное представление о времени. Например, в приведенном выше алгоритме я мог бы разрешить использование ряда «свободных» операций определенное количество раз. В приведенном выше алгоритме, если я определяю t ', исключая время для всего, кроме сна, тогда t' = 1 / n, что равно O (1 / n). Вероятно, есть лучшие примеры, поскольку асимптотическое поведение тривиально. На самом деле, я уверен, что кто-то может придумать чувства, которые дают нетривиальные результаты.

оборота Casebash
источник
1

Большинство остальных ответов интерпретируют big-O как исключительно время выполнения алгоритма. Но поскольку в вопросе об этом не упоминалось, я подумал, что стоит упомянуть другое применение big-O в численном анализе, которое связано с ошибкой.

Многие алгоритмы могут быть O (h ^ p) или O (n ^ {- p}) в зависимости от того, говорите ли вы о размере шага (h) или количестве делений (n). Например, в методе Эйлера вы ищете оценку y (h), учитывая, что вы знаете y (0) и dy / dx (производная от y). Ваша оценка y (h) тем точнее, чем ближе h к 0. Таким образом, чтобы найти y (x) для некоторого произвольного x, нужно взять интервал от 0 до x, разбить его до n частей и запустить метод Эйлера в каждой точке переходить от y (0) к y (x / n) к y (2x / n) и так далее.

Таким образом, метод Эйлера - это алгоритм O (h) или O (1 / n), где h обычно интерпретируется как размер шага, а n - как число делений интервала.

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

Для метода Эйлера, если вы используете числа с плавающей запятой, используйте достаточно маленький шаг и отмену, и вы добавляете небольшое число к большому, оставляя большое число без изменений. Для алгоритмов, которые вычисляют производную путем вычитания друг от друга двух чисел из функции, вычисленной в двух очень близких положениях, аппроксимирующих y '(x) с (y (x + h) - y (x) / h), в гладких функциях y (x + h) приближается к y (x), что приводит к большой отмене и оценке производной с меньшим количеством значащих цифр. Это, в свою очередь, будет распространяться на любой алгоритм, для которого требуется производная (например, краевая задача).

Андрей Лей
источник
0

Хорошо, я немного подумал об этом, и, возможно, существует алгоритм, который мог бы следовать этой общей форме:

Вам нужно вычислить задачу коммивояжера для графа 1000 узлов, однако вам также предоставляется список узлов, которые вы не можете посетить. По мере того, как список невидимых узлов увеличивается, проблема становится легче решать.

Shalmanese
источник
4
Это другой вид n в O (n) тогда. С помощью этого трюка можно сказать, что каждый алгоритм имеет O (q), где q - это количество людей, живущих в Китае, например.
Вава
2
Бойер-Мур имеет схожий вид (O (n / m)), но это не совсем «лучше, чем O (1)», потому что n> = m. Я думаю, что то же самое верно для вашего "невидимого TSP".
Ники
Даже в этом случае время выполнения TSP является NP-Complete, вы просто удаляете узлы из графа и, следовательно, эффективно уменьшаете n.
Эд Джеймс
0

Я вижу алгоритм, который по общему признанию равен O (1 / n):

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

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

Это имеет худшую производительность бесконечности, но средняя производительность падает, когда пространство данных заполняется.

Лорен Печтель
источник
0

При численном анализе алгоритмы аппроксимации должны иметь субконстантную асимптотическую сложность в допуске аппроксимации.

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}
Сэм Харвелл
источник
Вы действительно имеете в виду подконстантный или сублинейный? Почему алгоритмы аппроксимации должны быть непостоянными? И что это вообще значит ??
LarsH
@LarsH, ошибка алгоритмов аппроксимации пропорциональна размеру шага (или его положительной степени), поэтому чем меньше размер шага, тем меньше ошибка. Но другим распространенным способом изучения проблемы аппроксимации является ошибка по сравнению с тем, сколько раз делится интервал. Количество разделов в интервале обратно пропорционально размеру шага, поэтому ошибка обратно пропорциональна некоторой положительной степени количества разделов - при увеличении количества разделов ваша ошибка уменьшается.
Андрей Лей
@AndrewLei: Wow, ответ почти 7 лет спустя! Теперь я понимаю ответ Сэма лучше, чем тогда. Спасибо за ответ.
LarsH
0

Я думаю, что меньше, чем O (1) невозможно. Любое время, занимаемое алгоритмом, называется O (1). Но для O (1 / n), как насчет функции ниже. (Я знаю, что есть много вариантов, уже представленных в этом решении, но я предполагаю, что у них всех есть некоторые недостатки (не основные, они хорошо объясняют концепцию). Так что вот один, просто для аргументации:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

Таким образом, при увеличении n функция будет занимать все меньше и меньше времени. Также гарантируется, что если input на самом деле равен 0, функция вернется навсегда.

Можно утверждать, что это будет ограничено точностью машины. таким образом, sinc eit имеет верхнюю границу, это O (1). Но мы также можем обойти это, взяв значения n и C в строку. И сложение и сравнение делается на строку. Идея состоит в том, что при этом мы можем уменьшить n сколь угодно малым. Таким образом, верхний предел функции не ограничен, даже если мы игнорируем n = 0.

Я также считаю, что мы не можем просто сказать, что время выполнения равно O (1 / n). Но мы должны сказать что-то вроде O (1 + 1 / n)

user1953366
источник
-1

Может быть возможно построить алгоритм, который является O (1 / n). Одним примером может быть цикл, который повторяет несколько кратных f (n) -n раз, где f (n) - это некоторая функция, значение которой гарантированно будет больше n, а предел f (n) -n, когда n приближается к бесконечности, равен нуль. Вычисление f (n) также должно быть постоянным для всех n. Я не знаю, как выглядит f (n) или какое приложение будет иметь такой алгоритм, на мой взгляд, однако такая функция могла бы существовать, но результирующий алгоритм не имел бы никакой цели, кроме как доказать возможность алгоритма с O (1 / п).

Greg
источник
Ваш цикл требует проверки, которая занимает по крайней мере постоянное время, поэтому полученный алгоритм имеет по крайней мере сложность O (1).
Стефан Райх
-1

Я не знаю об алгоритмах, но сложности меньше, чем O (1) появляются в рандомизированных алгоритмах. На самом деле, o (1) (мало o) меньше, чем O (1). Этот вид сложности обычно появляется в рандомизированных алгоритмах. Например, как вы сказали, когда вероятность какого-либо события имеет порядок 1 / n, они обозначают его как o (1). Или, когда они хотят сказать, что что-то происходит с высокой вероятностью (например, 1 - 1 / n), они обозначают это как 1 - o (1).

А. Машреги
источник
-2

Если ответ одинаковый независимо от входных данных, то у вас есть алгоритм O (0).

или, другими словами, - ответ известен перед отправкой входных данных - функция может быть оптимизирована - поэтому O (0)

Про
источник
В самом деле? Вам все еще нужно будет вернуть значение, так что не будет ли это O (1)?
Иоахим Зауэр
7
нет, O (0) подразумевает, что для всех входов требуется нулевое время. O (1) - постоянное время.
Пит Киркхам
-2

Нотация Big-O представляет наихудший сценарий для алгоритма, который отличается от типичного времени выполнения. Просто доказать, что алгоритм O (1 / n) является алгоритмом O (1). По определению
O (1 / n) -> T (n) <= 1 / n, для всех n> = C> 0
O (1 / n) -> T (n) <= 1 / C, так как 1 / n <= 1 / C для всех n> = C
O (1 / n) -> O (1), поскольку запись Big-O игнорирует константы (т. Е. Значение C не имеет значения)

Лоуренс Барсанти
источник
Нет: нотация Big O также используется для описания сценариев среднего и ожидаемого времени (и даже наилучшего). Остальное следует.
Конрад Рудольф
Обозначение «О» определенно определяет верхнюю границу (с точки зрения алгоритмической сложности это будет наихудший случай). Омега и Тета используются для обозначения лучшего и среднего случая соответственно.
Роланд Эвальд
2
Роланд: Это заблуждение; верхняя граница - это не то же самое, что наихудший случай, оба являются независимыми понятиями. Рассмотрим ожидаемое (и среднее) время выполнения hashtable-containsалгоритма, которое можно обозначить как O (1), а наихудший случай можно очень точно определить как Theta (n)! Омега и тэта могут просто использоваться для обозначения других границ, но для повторения : они не имеют никакого отношения к среднему или лучшему случаю.
Конрад Рудольф
Конрад: правда. Тем не менее, Omega, Theata и O обычно используются для выражения границ, и если рассматриваются все возможные входные данные, O представляет верхнюю границу и т. Д.
Роланд Эвальд
1
Тот факт, что O (1 / n) является подмножеством O (1), тривиален и непосредственно следует из определения. Фактически, если функция g является O (h), то любая функция f, которая является O (g), также является O (h).
Тобиас
-2

Ничто не меньше, чем O (1) нотация Big-O подразумевает наибольший порядок сложности для алгоритма

Если время выполнения алгоритма равно n ^ 3 + n ^ 2 + n + 5, то оно равно O (n ^ 3). Более низкие степени здесь вообще не имеют значения, поскольку при n -> Inf n ^ 2 не будет иметь значения по сравнению с п ^ 3

Точно так же, как n -> Inf, O (1 / n) будет неактуальным по сравнению с O (1), следовательно, 3 + O (1 / n) будет таким же, как O (1), таким образом делая O (1) наименьшим возможным вычислительным сложность

user112831
источник
-2
inline void O0Algorithm() {}
STH
источник
1
Это был бы алгоритм O (1).
Лассе В. Карлсен
2
Это также, но дело в том, что это не Ω (1). И почему мой ответ был понижен? Если вы думаете, что я не прав, как насчет объяснения?
Стюарт
В другом месте я спрашивал, является ли этот ответ правильным или нет, и, похоже, это оспаривается: stackoverflow.com/questions/3209139/…
jyoungdev
Ну, это встроенный, так что вы можете рассмотреть это O (0). Однако все алгоритмы O (0) тривиальны (ничего не делают), так что ... не очень интересный ответ.
Стефан Райх
@StefanReich Правда, это не очень интересный ответ, но это ответ.
Стюарт
-2

Вот простой алгоритм O (1 / n). И это даже делает что-то интересное!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

O (1 / n) возможно, поскольку оно описывает, как выходные данные функции изменяются при увеличении размера ввода. Если мы используем функцию 1 / n для описания количества инструкций, которые выполняет функция, тогда не требуется, чтобы функция принимала нулевые инструкции для любого размера ввода. Скорее, дело в том, что для каждого входного размера, n выше некоторого порога, количество требуемых инструкций ограничено сверху положительной константой, умноженной на 1 / n. Поскольку нет фактического числа, для которого 1 / n равно 0, а константа положительна, то нет никаких причин, по которым функция будет вынуждена принимать 0 или меньше инструкций.

ejspencer
источник
1
Поскольку O (1 / n) упадет ниже горизонтальной линии = 1, а когда n достигнет бесконечности, ваш код все равно будет выполнять заданное количество шагов, этот алгоритм является алгоритмом O (1). Нотация Big-O является функцией всех различных частей алгоритма, и она выбирает самую большую. Так как метод всегда будет выполнять некоторые инструкции, когда n достигает бесконечности, вы останетесь с теми же самыми инструкциями, выполняющимися каждый раз, и, следовательно, метод будет выполняться в постоянное время. Конечно, это не займет много времени, но это не относится к нотации Big-O.
Лассе В. Карлсен