algorithm - アルゴリズムの分析 (N^2)

Question

最悪のランタイム Θ(n^2) でアルゴリズムを実行する必要があります。その後、実行するたびに Θ(n^2) のランタイムでアルゴリズムを 5 回実行する必要があります。

これらのアルゴリズムを組み合わせた最悪の実行時間は?

私の頭では、式は次のようになります。

( N^2 + (N^2 * 5) )

しかし、シータ表記で分析する必要がある場合、私の推測では、それは Θ(n^2) 時間で実行されます。

私は正しいですか？

Answer 1

2 回 O(N^2) はまだ O(N^2)、10 回 O(N^2) はまだ O(N^2)、5 回 O(N^2) はまだ O(N^2) 、'any' が定数である限り、いつでも O(N^2) は O(N^2) のままです。

O の代わりに \Theta についても同じ答えが当てはまります。

Answer 2

O(n^2)あなたが持っているのは基本的に であるため、それは関係ありませんO(6n^2)。これは、O(n^2)定数を無視できるためです。あなたが見ているのは、関数そのものではなく、一連の関数に属するものです。

基本的に、6n^2 ∈ O(n^2).

編集

Θについても尋ねました。Θ は下限と上限を示しますが、O は上限のみを示します。Ω でのみ下限が得られます。Θ はこれら 2 つの交点です。

であるものはすべて ですが、その逆でΘ(f(n))はありO(f(n))ません。