Сначала нам нужно уточнить, что мы подразумеваем под «имеет ли это место, если мы имеем бесконечную цепь?». Мы рассматриваем его как бесконечную последовательность функций , что для всех имею . Такая последовательность может не иметь последней функции.{fi:N→N∣1≤i}ifi(n)=O(fi+1(n))
Мы можем посмотреть на предел функций в последовательности, т.е. . Однако возможно, что этот предел не существует. И даже в том случае, если он существует, у нас может не быть . Например, рассмотрим последовательность функций . Для каждого ,
и , следовательно . Однако
таким образом, .f∞(n)=limi→∞fi(n)f1(n)=O(f∞(n))fi(n)=niifi(n)=Θ(n)fi(n)=O(fi+1(n))f∞(n)=limi→∞fi(n)=0=Θ(1)f1(n)≠O(f∞(n))
С другой стороны, мы можем посмотреть на предел последовательности классов, который не должен быть равен классу предела функций . У нас есть , поэтому и для всех . Верхний предел содержит все элементы (функции в данном случае), которые встречаются бесконечно часто, а нижний предел содержит все элементы, которые встречаются во всех для некоторыхfi∈O(fi+1)O(fi)⊆O(fi+1)fj∈limi→∞O(fi)=lim supi→∞O(fi)=lim infi→∞O(fi)=⋃n∈N⋂k>nO(fk)jO(fi),i≥n0n0 (который может зависеть от элемента). Поскольку последовательность классов монотонно возрастает, оба существуют и они равны. Это оправдывает использование .lim
Существует две серии: одна из функций (которые могут сходиться или нет) и одна из множеств (где каждый набор является супернабором предыдущего; именно поэтому эта серия сходится - см. Определение lim inf и lim sup для множеств) , Первая часть отвечает на вопрос без части , вторая часть отрицательно отвечает на часть (если - это разновидность лаймов). f∞f∞f∞
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,…,fnf∞fiNR+f∞(x)=max{fn(x)∣n∈N}{fn(x)∣n∈N}
f∞(x)=max{fn(x)∣1≤n≤N}if N≤x<N+1
Тогда для любого , , так . Если вам нужна функция, которая растет строго быстрее ( ), возьмите .NfN∈O(f∞)∀x≥N,f∞(x)≥fN(x)f∞=o(f′∞)f′∞(x)=x⋅(1+f∞(x))
Все эти ответы (ваши и другие) основаны на предположении, что мы знаем, что происходит в бесконечности, они не удовлетворяют меня, я не знаю об ОП (почему у нас не должно быть закрытой группы с бесконечным размером) ?)
4
@SaeedAmiri Извините, я не понимаю ваш комментарий: что вы подразумеваете под «мы знаем, что происходит в бесконечности, они не удовлетворяют меня»?
Да, возможно иметь бесконечную цепь.
Я уверен, что вы уже знакомы с некоторыми примерами: У вас здесь бесконечная цепочка: полиномы растущей степени. Вы можете пойти дальше? Конечно! Экспонента растет быстрее (асимптотически), чем любой многочлен. И, конечно, вы можете продолжать:
Вы можете построить бесконечную цепочку и в другом направлении. Если то (придерживаясь положительных функций, поскольку здесь мы обсуждаем асимптотику функций сложности). Итак, мы имеем, например:f=O(g) 1g=O(1f)
Фактически, для любой цепочки функций вы можете создать функцию которая будет расти быстрее всех из них. (Я предполагаю, что являются функциями от до .) Сначала начните с идеи . Это может не сработать, потому что множество может быть неограниченным. Но поскольку мы заинтересованы только в асимптотическом росте, достаточно начать с малого и постепенно расти. Возьмите максимум за конечное число функций.f1,…,fn f∞ fi N R+ f∞(x)=max{fn(x)∣n∈N} {fn(x)∣n∈N}
источник