algorithm - ビッグオーとビッグオメガの入れ方

Question

アルゴリズムに 2 つのサブ アルゴリズムがある場合、与えられた入力に対してサブ アルゴリズム A1 が最良のケースである場合、サブ アルゴリズム A2 は最悪のケースです。全体的なアルゴリズムの複雑さを知るにはどうすればよいですか? 簡単に言うと、Ω(N) + O(N)=? アルゴリズムが順次実行されているかどうかは、全体の複雑さが O(N)+ O(N) であり、ネストされた順序で O(N)* O(N) であるかどうかを知っています。

シーケンシャルと入れ子の両方の場合について教えてください

Answer 1

基本的に Ω(N) + O(N)= Ω(N) です。O(N) は Ω(N) の次数が低い (または最大で同じ) ことを意味するためです。合計すると、下位は省略できます。

Answer 2

アルゴリズムに (たとえば) O(N) 時間かかる操作と O(N^2) 時間かかる別の操作が含まれている場合、全体的な複雑さは O(N^2) になります。O(N^2 + N)というものはありません。Ω() も同様です。これは、「順次実行順序」に関する質問に答えます。

アルゴリズムに N 個の操作が含まれ、それぞれに O(N) 時間がかかる場合、全体的な複雑さは O(N^2) になります。Ω() も同様です。多項式を乗算し、N の増加に伴って最も急速に成長する項を取得するだけです。これは、「ネストされた実行順序」に関する質問に答えます。