algorithm - 特定のプログラムの時間計算量を見つけるためのプログラム/アルゴリズム

Question

私は、「プログラムまたはアルゴリズムを書く」ことが可能かどうかを知りたいと思っています。

入力 :任意のプログラム (P) [任意の言語または特定の言語の]

出力 :そのプログラムの時間計算量 (P)。

そのようなプログラムを書く試みは以前にありましたか? この目的で利用できるアルゴリズムはありますか?

その場合は、必要なリンク、参照、または可能なあらゆる種類のガイダンスを提供してください。

Answer 1

いいえ、できません。これは停止問題の一形態です。

Answer 2

任意のアルゴリズムの複雑さを証明することはできませんが、原則として推定することはできます。

1. 入力のサイズ n を選択します
2. アルゴリズムを実行する
3. サイズ n の入力に対してアルゴリズムを実行するのに必要な時間 t(n) を観察する
4. 別の n を選択し、大量のデータが得られるまで手順 2 と 3 を繰り返します
5. n、n^k、log(n)、n log(n)、n!、またはその他の適切な用語で t(n) を回帰します。
6. 統計的に有意な用語を選択し、それがアルゴリズムの推定複雑度であると宣言します

このアプローチにはいくつもの落とし穴があります

1. これは何も証明しません。推定のみです
2. 大きい n に対して t(n) が非常に大きくなると、分析に十分なデータを収集するのに長い時間がかかります。

3. 巨大な値の n を使用しない限り、このアプローチはだまされる可能性がたくさんあります。たとえば、このアルゴリズムは、n に天文学的な値を使用しない限り、O(1) のように見えます。

   sleep for 10 days
   run an O(n log(n)) sorting algorithm
   

そして、他の SO ユーザーは、さらに多くのことを考え出すことができます。しかし、アルゴリズムの複雑さの分析を行って経験的に検証したい場合など、場合によっては、これは依然として有用なアプローチです。

Answer 3

アルゴリズム自体にさらにいくつかの変数を導入して、手動で行うのと同じ方法で複雑さを見つけることはできませんか? たとえば、アルゴリズムのループ部分全体を追跡し、O(n^2) として答えを与える n=0 という挿入ソートの変数を使用できます。

Answer 4

まあ、すべてのケースを想定してこれを行うと思います。1:まず命令ごとに抽出できるモジュールを作るように 2:プログラムの命令に対応する命令のデータベースを作る。3: データベースで設定した適切な時間複雑度を取得して複雑度を計算します。それだけです。