これはおそらくbig-O表記に関する初心者の質問だと思います。たとえば、リスト全体を再帰的に分解し (O(n))、それを元に戻す (O(n)) アルゴリズムがあるとします。これは、効率が O(n) + O(n) であることを意味すると仮定します。これは 2O(n)、O(2n)、または O(n) に単純化されますか? この表記法について私が知っていることから、それは O(2n) であり、漸近表記法の規則を使用して 2 を削除すると、O(n) の効率が得られます。
しかし、下限を見つけようとしていた場合、このルールは適用できるでしょうか? Ω(n) + Ω(n) = Ω(2n) の場合、2 を削除できますか? 実際には下限を下げることになるので（n < 2nなので）、そうではないと思います。
これは 2O(n)、O(2n)、または O(n) に単純化されますか?」
上記のすべてですが、最初の 2 つは非常に複雑です。O(n) は正規表記になります。
2*N は N に比例するため、十分に大きな N ( O(2*N) ) に対して最大コストが 2*N に比例するだけである場合、最大コストも十分に大きい N に比例するだけです。大きな N ( O(N) )。
しかし、下限を見つけようとしていた場合、このルールは適用できるでしょうか?
間違いなくそうです。
2*N は N に比例するため、十分に大きな N ( Ω(2*N) ) に対して最小コストが 2*N に比例する以上であれば、最小コストも十分に N に比例することになります。大きな N ( Ω(N) )。
たとえば、実行に 300 ミリ秒 + 100*N ミリ秒かかるアルゴリズムがあるとします。その速度の下限は Θ(N) であり、したがって Ω(N) です。
アルゴリズムの実行に 2 倍の時間がかかる場合はどうなるでしょうか? 実行に 600 ミリ秒 + 200*N ミリ秒かかったとしても、その速度の下限は依然として Θ(N) であり、したがって Ω(N) です。
Θ(N) などを理解するために実現する最も重要なことは、これらの表記法を使用して何かがどれだけうまくスケールするかを調べることです。あるアルゴリズムは、別のアルゴリズムの 2 倍の時間がかかりますが、スケーリングの程度については何も言わないため、速度の下限に同じ Ω() を使用できることは驚くべきことではありません。
問題を解決するのにかかる時間は問題のサイズに比例することを示します。この場合、意味は同じですが、2O(n) と書いた方が適切かもしれません。
しばらく経ちましたが、どちらの場合も正しいと思います。
アップデート
実際には Ω(n) + Ω(n) == Ω(n) のように見えます
Big-O の定義によると、私は次のように考えています。
関数 f(n) が、定数 c と n の十分に大きな値に対して <= cg(n) である場合、f(n) = O(g(n)) と言えます。あなたの例では、g(n) = n.
したがって、たとえば、十分に大きな n に対して f(n) <= cn となる c の値を選択できる場合、f(n) = O(n) と言えます。
ビッグオメガも同様に定義されています。