AsymptoticLessEqual

AsymptoticLessEqual[f,g,xx^*]

xx^*のときにまたはとなる条件を与える．

AsymptoticLessEqual[f,g,{x₁,…,x_n}{,…,}]

{x₁,…,x_n}{,…,}のときにまたはとなる条件を与える．

詳細とオプション

「漸近的に以下」は，f が g のbig-oである，f の上限は g である，f の次数は最大でも g である，f は最高で g と同速さで大きくなる等と表現される．点 x^*はコンテキストから推測されることが多い．
「漸近的に以下」は順序関係で，である定数について x が x^*の近くにあるときにであることを意味する．
点の近くの関数や級数の単純な上限を表すために，また，方程式の解や複雑な計算の単純な上限を表すためにしばしば使われる．
有限極限点の x^*および{,…,}については以下のようになる．

	AsymptoticLessEqual[f[x],g[x],xx^*]	$0<TemplateBox[{{x, -, {x, ^, }}}, Abs]<delta(c,x^)$ がを意味するとが存在する
	AsymptoticLessEqual[f[x₁,…,x_n],g[x₁,…,x_n],{x₁,…,x_n}{,…,}]	$0<TemplateBox[{{{, {{{x, _, 1}, -, {x, _, 1, ^, }}, ,, ..., ,, {{x, _, n}, -, {x, _, n, ^, }}}, }}}, Norm]<delta(c,x^*)$ が $TemplateBox[{{f, (, {{x, _, 1}, ,, ..., ,, {x, _, n}}, )}}, Abs]<=c TemplateBox[{{g, (, {{x, _, 1}, ,, ..., ,, {x, _, n}}, )}}, Abs]$ を意味するなとが存在する

無限極限点については以下のようになる．

	AsymptoticLessEqual[f[x],g[x],x∞]	がを意味するとが存在する
	AsymptoticLessEqual[f[x₁,…,x_n],g[x₁,…,x_n],{x₁,…,x_n}{∞,…,∞}]	が $TemplateBox[{{f, (, {{x, _, 1}, ,, ..., ,, {x, _, n}}, )}}, Abs]<=c TemplateBox[{{g, (, {{x, _, 1}, ,, ..., ,, {x, _, n}}, )}}, Abs]$ を意味するとが存在する

g[x]が x^*付近に0の無限集合を持たない場合，AsymptoticLessEqual[f[x],g[x],xx^*]はMaxLimit[Abs[f[x]/g[x]],xx^*]<∞のときかつそのときに限り存在する．
次は，使用可能なオプションである．

Assumptions	$Assumptions	パラメータについての仮定
Direction	Reals	極限点に近付く方向
GenerateConditions	Automatic	パラメータについての条件を生成する
Method	Automatic	使用するメソッド
PerformanceGoal	"Quality"	何を最適化するか

次は，Directionの可能な設定である．

	Reals または "TwoSided"	両実数方向から
	"FromAbove" または -1	上，つまり大きい値から
	"FromBelow" または +1	下，つまりは小さい値から
	Complexes	すべての複素方向から
	Exp[ θ]	の方向
	{dir₁,…,dir_n}	変数 x_iに方向 dir_iを使う

x^*におけるDirectionExp[ θ]は，曲線の接線が極限点 x^*に近付く方向を示す．

次は，GenerateConditionsの可能な設定である．
Automatic 一般的ではない条件のみ

True すべての条件

False 条件なし

None 条件が必要な場合には未評価で返す
PerformanceGoalの可能な設定には，$PerformanceGoal，"Quality"，"Speed"がある．"Quality"設定のとき，Limitはより多くの問題を解いたりより簡単な結果を与えたりすることが多いが，より多くの時間とメモリが必要になる可能性がある．

例題

すべて開くすべて閉じる

例 (2)

のときに，であることを検証する：

2つの関数を可視化する：

{x,y}->∞のときに，であることを検証する：

2つの関数を可視化する：

スコープ (9)

厳密には正ではない関数を比較する：

が原点でと同じくらい速く発散することを示す：

答は，明示的なTrueまたはFalseではなく，ブール式かもしれない：

パラメータを含む関数を比較する場合は，結果についての条件が生成されることがある：

デフォルトで，関数の両側比較が行われる：

のより大きい値を比較する場合は，は実際に $x^2 TemplateBox[{{x}}, UnitStepSeq]$ と同じくらいである：

この関係は，のより小さい値については成り立たない：

2つの関数を可視化する：

Sqrtのような関数は，負の実数に沿って両方の実数方向で同じ関係があるかもしれない：

複素平面で上から近付く場合には，同じ関係が見られる：

しかし，複素平面で下から近付く場合は異なる結果になる：

これは，軸が交差するときにSqrtの虚部の符号が逆になるところで分枝切断があるためである：

したがって，この関係は，一般に，複素平面では成り立たない：

4つの実数および複素数の方向から近付く場合の関数の相対サイズを可視化する：

多変量関数を比較する：

2つの関数のノルムを可視化する：

多変量関数を無限大で比較する：

多変量関数を比較する際にパラメータを使用する：

オプション (10)

Assumptions (1)

Assumptionsを使ってパラメータについての条件を指定する：

仮定が異なると結果も異なるかもしれない：

Direction (5)

下からの関係を判定する：

同様に：

上からの関係を判定する：

同様に：

区分ごとの不連続点での関係を判定する：

片方の方向でうまくいかないので，両方からもうまくいかない：

2関数とその割合を可視化する：

単純極における関係は近付く方向には無関係である：

分枝切断線における関係を判定する：

異なる象限から近付く際の関係を計算する：

第1象限から原点に近付く：

同様に：

右半平面から原点に近付く：

下半平面から原点に近付く：

関数の割合を可視化する：

GenerateConditions (3)

条件を述べずに結果を返す：

この結果は n>0のときにのみ有効である：

結果がパラメータの値に依存するときは，未評価で返される：

デフォルトで，結果を保証する条件が生成される：

デフォルトで，特殊な値でしか結果が無効にならない場合は，条件は生成されない：

GenerateConditions->Trueのときは，これらの一般的ではない条件も報告される：

PerformanceGoal (1)

PerformanceGoalを使って潜在的に高価な計算を回避する：

デフォルト設定では，使用可能なすべての手法を使って結果を出そうとする：

アプリケーション (10)

基本的なアプリケーション (4)

0においてであることを示す：

これを記号的に示す：

この関数を可視化する：

この関係はすべての実数ベキに及ぶ：

階乗ベキと負のベキで関数を可視化する：

∞においてであることを示す：

これを記号的に示す：

この関係を対数プロットで可視化する：

この関係はすべての実数ベキに及ぶ：

階乗ベキと負のベキで関数を可視化する：

0においてであることを示す：

3つの関数を可視化する：

∞においてであることを示す：

3つの関数を可視化する：

計算の複雑性 (4)

単純なソートアルゴリズム（バブルソート，挿入ソート）は n 個のオブジェクトをソートするのに約 a n²ステップを要する．これに対し，最適化された一般的アルゴリズム（ヒープソート，マージソート）はソートを行うのに約 b n Log[n]のステップを要する．大量のオブジェクトに対しては，最適化されたアルゴリズムの方がソート時間が長くなることは決してない，つまりであることを示す：

ある種の特別なアルゴリズム（分布数え上げソート，基数ソート）は，考えられる入力についての情報が事前に分かっているので，c n 時間で実行することができる．であることを示す：

3つの時間スケールの増大を可視化する：

バブルソートでは，隣接近傍が比較され，順序が狂っている場合には入れ替えられる．1回のパス（n-1 回の比較）の後で最大要素が末尾になる．このプロセスが残りの n-1個の要素に対して行われ，先頭の2つの要素が残るまでこれが繰り返される．比較と入替えが c ステップだとすると，ソートのステップ総数は次のようになる：

多項式はにある：

にもある：

したがって，であり，このアルゴリズムのランタイムは2次であると言われる：

マージソートでは，要素のリストが2つに分割され，半分ずつソートされ，最後に2つの部分が結合される．であるから，ソート時間T[n]は中間を計算する一定の時間 b，各半分を計算する時間2T[n/2]，2つの半分を結合するための要素数の倍数 a n の合計になる：

再帰方程式を解いて n 個の要素をソートする時間 t を求める：

であることを示す：

逆に，：

したがってであり，このアルゴリズムのランタイムはであると言われる：

巡回セールスマン問題(TSP)は個の都市を繋ぐ最短経路を求めるものである．馬鹿正直なアルゴリズムは通りの経路すべてを試そうとする．Held–Karpアルゴリズムは，それよりも効率よく約ステップに短縮する．であることを示す：

どちらのアルゴリズムも巡回セールスマン問題の複雑性クラスは，時間で解ける問題のEXPTIMEと同じくらいであることを示している．Held–Karpアルゴリズムは，のを使うだけで十分である：

階乗については，のようにより高次の多項式を使う必要がある：

解の近似は回で求まるので，巡回セールスマン問題の近似は多項式時間で可解な問題の複雑性クラスPに属する．どの多項式アルゴリズムも指数アルゴリズムより速い．つまりである：

収束判定法 (2)

$sum_(n=1)^inftyTemplateBox[{{a, _, n}}, Abs]<infty$ であれば，列は絶対加算可能であると言われる．第2列がなら，比較判定法は，が絶対加算可能ならも絶対加算可能であると述べる．この判定法を使って，の総和と比較することによってが収束することを示す：

が収束するように，関心の総和も収束する：

SumConvergenceが与える答と比較する：

と比較可能な別の列に $TemplateBox[{n}, PrimePi]/(n^3log(n))$ がある．したがって，これも絶対加算可能である：

の和と比較することで，が収束することを示す：

$int_a^bTemplateBox[{{f, , {(, x, )}}}, Abs]dx<infty$ なら，関数はで完全に積分可能であると言われる．とが開区間で連続であり，との両方でなら，比較判定法はが完全に積分可能ならもそうであるとする．この判定法を使ってがで完全に積分可能であることを示す：