4

私は、自分の時間計算量を推論できるプログラミング言語に興味があります。この目的のために、プログラムで時間計算量を表す何らかの方法があると非常に便利です。これにより、次のようなことが可能になります。

f_time = O(n)
g_time = O(n^2)
h_time = O(sqrt(n))

fastest_asymptotically = min(f_time, g_time, h_time)  # = h_time
total_time = f_time.inside(g_time).followed_by(h_time)  # = O(n^3)

現在Pythonを使用していますが、特に言語に縛られているわけではありません。私はsympyを試しましたが、箱から出して必要なものを見つけることができませんでした。

この機能を提供するライブラリはありますか？そうでない場合は、記号数学ライブラリを使用して上記を行う簡単な方法はありますか？

編集：@ Patrick87のアドバイスに従って簡単なライブラリを作成しましたが、機能しているようです。ただし、この問題に対する他の解決策があるかどうかはまだ興味があります。

4

3 に答える 3

4

SymPyは現在、0での拡張のみをサポートしています（シフトを実行することで他の有限点をシミュレートできます）。アルゴリズム解析で使用される無限大での拡張はサポートされていません。

しかし、それはそれにとって良い基本パッケージであり、あなたがそれを実装すれば、私たちは喜んでパッチを受け入れます（nb：私はSymPyコア開発者です）。

特に2つの変数、またはシンボリック定数がある場合は特に、問題が難しいことに注意してください。振動機能をサポートしたい場合にも注意が必要です。編集：あなたが振動関数に興味があるなら、このSymPyメーリングリストの議論はいくつかの興味深い論文を提供します。

編集2：数式処理システムを使用せずに、これを最初から作成しようとしないことをお勧めします。自分で数式処理システムを作成する必要がありますが、これは大変な作業であり、正しく実行し、速度を落とさないようにするには、さらに多くの作業が必要になります。その上に構築されるコードのライブラリとして機能できるシステム（SymPyなど）を含め、すでに多数のシステムが存在しています。

于 2013-01-25T17:56:15.400 に答える
1

big-O表記のみを使用していて、漸近的に言えば、ある関数が別の関数よりも速く成長するかどうかに関心がある場合...

  1. 与えられた関数fとg
  2. 数式処理パッケージを使用して、nがf（n）/ g（n）の無限大になるときの制限を計算します。
  3. 限界が+無限大に発散する場合、g = O（f）であるという意味で、f> g-ですが、f！= O（g）です。
  4. 限界が0に発散する場合、g<fです。
  5. 限界が有限数に収束する場合、f = g（f = O（g）およびg = O（f）という意味で）
  6. 制限が定義されていない場合...私を打ち負かします！
于 2013-01-24T21:02:02.220 に答える
1

実際には、以下を処理できる式の簡略化を構築/検索しています。

  • +（あなたの言葉でfollowed_by:)
  • *****（あなたの言葉でinside:)
  • ^、ログ、！（複雑さを表すため）
  • 変数（nなどm）
  • 定数（のように2^n）

たとえば、あなたが与えf_time.inside(g_time).followed_by(h_time)たように、それは次のような式である可能性があります：

n*(n^2)+(n^(1/2))

、そしてあなたはそれを次のように出力するようにプロセッサを期待しています：n^3。

したがって、一般的に言えば、一般的な式の簡略化を使用して（面白くしたい場合は、Mathemeticaがどのように行うかを確認してください）、のような簡略化された式を取得するn^3+n^(1/2)ことができます。次に、次の用語を選択するための追加のプロセッサが必要です。式から最も複雑になり、他の用語を取り除きます。それは簡単です。テーブルを使用して、各種類のシンボルの複雑さの順序を定義するだけです。

stringこの場合、式は単なる記号であることに注意してください。関数としてではなく、 （たとえば:)のように記述する必要がありf_time = "O(n)"ます。

于 2013-01-24T21:12:15.507 に答える