アルゴリズムの実行時間を確認する方法は？

Question

アフィンギャップコストを使用してグローバルアライメントアルゴリズムをコーディングしました。 big-O表記でアルゴリズムを実行する時間はO（n^2）です。しかし、クラスの私の先生は、実行時間を確認するために、実行時間をn^2（nはシーケンスの長さ）で除算しなければならないと言っています（異なる長さのシーケンスを使用しています。）。そして（n、R（n）/ n^2）が水平線より下にある場合、実行時間が確認されます。私はそれが意味することを本当に理解できませんでした。私は異なる長さのシーケンスを使ってR（n）/ n^2をプロットしました。そしてそれは働いた。私は最初に変動があったが、変動がなくなった（これも画像で見ることができる）。私が使用した配列は、1000塩基長〜10,000塩基長であった。 R（n）/ n^2が実行時間をどのように確認することができますか？私はインターネットで見てみましたが、可能な答えを見つけることができませんでした。もし私の質問が単純すぎるなら、私を許してください。私はコンピュータ科学のバックグラウンドを持っていません。

Answer 1

Oは（N ）関数のセットR（N）、例えばR（N）  ≤ 、Cある定数ため、そのように定義されます  cn すべてが十分に大きいnです。不等式が^R（N）C/_N   ≤   と等価であること

。

だからあなたの先生はあなたが十分に大きいNのために、あなたは（大体）一定のを得る、ことを確認するために^R（N）/_Nをプロットすることを示唆していますc。

このプロットは正式な証明ではありません。それは単なる有用な視覚化です。

Answer 2

アルゴリズムがO（n²）の場合、実際には入力サイズnの関数としてアルゴリズムを実行するのに必要なステップ数がO（n²）であることを意味します。

関数がO（n²）内にあると言うとき、実際には正の定数cがあるので、大きな入力サイズの場合はf(n) < c * n²となります。

これは、正の定数cが存在するため、入力サイズが大きい場合はc > f(n)/n²となります。

上記のグラフが一定の値に収束していることに気が付きました。これはあなたのcです。

もちろん、アルゴリズムを実行するのに必要なステップ数はdepend on the machineです。

Answer 3

さらに簡単に説明すると、O（n²）のアルゴリズムは2次関数に似ています。常に2次関数をa *b²の形式の関数で除算して定数関数を得ることができます。

Answer 4

いくつかの数学。

1）はG（N）= F（N）/ N ^{を定義します（。申し訳ありませんが、あなたが本当にこれを理解するために数学のビットを必要としない）}

表記f(n)がO(n^2)であることを意味します2

2）NはGの無限大になる傾向があるように制限（n）はCが直感的にいくつかの定数

あるC、あるg(n)関数が近づくと近づくと言うことCとしてnが大きくなります。数学者は、それがCに「収束する」と言うだろう。

（実際には、数学はそれよりも少し複雑ですが、私は非常にさびだ。そして、私はこの単純なを維持しようとしている。）

あなたのグラフはそのグラムを実証に何をしていますか（n）は実際に収束する。そして、Cの値は、グラフが近づいている直線に対応するY軸上の値です.X軸の値が無限大になると値になります。

Answer 5

Oである実行時間は（N^2）常に2つの実数正数BとN0そのようなすべてのN> = N0、

R（n）のための、それが存在することを意味< = b *（n^2）ここで、R（n）は実行時間関数です。

つまり、実行時間はb *（n^2）という形式の関数よりも低くなります。

---

あなたはその不平等を取り、（N^2）ですべてを分割する場合は、あなたが得る：

R（N）/（N^2）< = B

とビッグO定義はそのまま適用されます。

ように長いRは、（N）/（N^2）N> = N0ためB以下に留まるように、次にR（n）はO（N^2）です。再び言い換えれば、これは定数関数b（水平線）より下にあることを意味します。

あなたがやっていることは、R（n）/ n^2をプロットして、グラフが水平に安定しているかどうかを確認することです。十分に高いです。n。

これはR（n）をプロットし、グラフがおよそ2次関数であるかどうかを確認するよりも簡単です（2次関数は3次および高次多項式に非常に似ていますが、同意しないのですか？ R（n）が実際にO（n^3）だった場合、R（n）/（n^2）は三日月関数を与え、