Бесконечная цепочка больших

12

Во-первых, позвольте мне написать определение большого чтобы сделать вещи явными.O

f(n)O(g(n))c,n0>0 такое, что0f(n)cg(n),nn0

Допустим, у нас есть конечное число функций: удовлетворяющих:f1,f2,fn

O(f1)O(f2)O(fn)

В силу транзитивности имеем:OO(f1)O(fn)

Имеет ли это место, если у нас есть бесконечная цепочка Os ? Другими словами, O(f1)O(f) ?

У меня проблемы с представлением, что происходит.

saadtaame
источник

Ответы:

15

Сначала нам нужно уточнить, что мы подразумеваем под «имеет ли это место, если мы имеем бесконечную цепь?». Мы рассматриваем его как бесконечную последовательность функций , что для всех имею . Такая последовательность может не иметь последней функции.{fi:NN1i}ifi(n)=O(fi+1(n))

Мы можем посмотреть на предел функций в последовательности, т.е. . Однако возможно, что этот предел не существует. И даже в том случае, если он существует, у нас может не быть . Например, рассмотрим последовательность функций . Для каждого , и , следовательно . Однако таким образом, .f(n)=limifi(n)f1(n)=O(f(n))fi(n)=niifi(n)=Θ(n)fi(n)=O(fi+1(n))f(n)=limifi(n)=0=Θ(1)f1(n)O(f(n))

С другой стороны, мы можем посмотреть на предел последовательности классов, который не должен быть равен классу предела функций . У нас есть , поэтому и для всех . Верхний предел содержит все элементы (функции в данном случае), которые встречаются бесконечно часто, а нижний предел содержит все элементы, которые встречаются во всех для некоторыхfiO(fi+1)O(fi)O(fi+1)fjlimiO(fi)=lim supiO(fi)=lim infiO(fi)=nNk>nO(fk)jO(fi),in0n0 (который может зависеть от элемента). Поскольку последовательность классов монотонно возрастает, оба существуют и они равны. Это оправдывает использование .lim

frafl
источник
3
Существует две серии: одна из функций (которые могут сходиться или нет) и одна из множеств (где каждый набор является супернабором предыдущего; именно поэтому эта серия сходится - см. Определение lim inf и lim sup для множеств) , Первая часть отвечает на вопрос без части , вторая часть отрицательно отвечает на часть (если - это разновидность лаймов). fff
13
Что если количество терминов неисчислимо? :)
SamM
Используете ли вы упорядочивание или вы хотите заменить серию чем-то более непрерывным? :)
frafl
@Kaveh Большое спасибо, теперь это имеет смысл. Если бы вы могли оправдать использование пределов и то, что означает это понятие, то это завершит мое понимание.
saadtaame
1
@saadtaame: Может быть, это потому, что вопрос выше все еще не спрашивает, что вы хотите знать? Если я правильно помню, вы добавили из-за предложенного комментария. Если вы предоставите некоторый контекст, возможно, кто-то может перефразировать вопрос еще раз. f
13
5

Да, возможно иметь бесконечную цепь.

Я уверен, что вы уже знакомы с некоторыми примерами: У вас здесь бесконечная цепочка: полиномы растущей степени. Вы можете пойти дальше? Конечно! Экспонента растет быстрее (асимптотически), чем любой многочлен. И, конечно, вы можете продолжать:

O(x)O(x2)O(x42)
O(x)O(x2)O(x42)O(ex)
O(ex)O(xex)O(e2x)O(eex)

Вы можете построить бесконечную цепочку и в другом направлении. Если то (придерживаясь положительных функций, поскольку здесь мы обсуждаем асимптотику функций сложности). Итак, мы имеем, например:f=O(g)1g=O(1f)

O(x)O(x2)O(exx2)O(exx)O(ex)

Фактически, для любой цепочки функций вы можете создать функцию которая будет расти быстрее всех из них. (Я предполагаю, что являются функциями от до .) Сначала начните с идеи . Это может не сработать, потому что множество может быть неограниченным. Но поскольку мы заинтересованы только в асимптотическом росте, достаточно начать с малого и постепенно расти. Возьмите максимум за конечное число функций. f1,,fnffiNR+f(x)=max{fn(x)nN}{fn(x)nN}

f(x)=max{fn(x)1nN}if Nx<N+1
Тогда для любого , , так . Если вам нужна функция, которая растет строго быстрее ( ), возьмите .NfNO(f)xN,f(x)fN(x)f=o(f)f(x)=x(1+f(x))
Жиль "ТАК - прекрати быть злым"
источник
Все эти ответы (ваши и другие) основаны на предположении, что мы знаем, что происходит в бесконечности, они не удовлетворяют меня, я не знаю об ОП (почему у нас не должно быть закрытой группы с бесконечным размером) ?)
4
@SaeedAmiri Извините, я не понимаю ваш комментарий: что вы подразумеваете под «мы знаем, что происходит в бесконечности, они не удовлетворяют меня»?
Жиль "ТАК - перестань быть злым"