時間の複雑さを扱うときのT(N)との違いについて少し混乱しています。O(N)それぞれのT(N)方程式を持つ 3 つのアルゴリズムがあり、最悪の場合の時間計算量を見つけるO(N)必要があり、それが とどう違うのかわかりませんT(N)。
例は次のとおりです。
T(n) = 150⋅N² + 3⋅N + 11⋅log₂(N)
O()ちょうどでしょうかO(N²)
また、複雑度の低いアルゴリズムを常に使用する必要がありますか? 答えはノーだと思いますが、その理由はよくわかりません。
O() はただの O(N²) でしょうか?
はい。
N が大きい場合、N² 項が実行時間を支配するため、他の項はもはや問題になりません。
たとえば、N = 10 の場合、あなたの例では、150⋅N² はすでに 15000 ですが、3⋅N = 30 および 11⋅log₂(N) = 36.5 であるため、非 N² 項は合計数の 0.44% しか占めません。ステップ。
N=100、150⋅N² = 1500000、3⋅N = 300、11⋅log₂(N) = 73.1 の場合、N² 以外の項は総ステップ数の 0.025% しか占めません。
そのため、N が大きくなると、低次項の関連性が低下します。
また、複雑度の低いアルゴリズムを常に使用する必要がありますか?
いいえ。Big-O 表記法は、N が大きくなったときの漸近的な動作のみを記述し、一定係数のオーバーヘッドを含まないため、オーバーヘッドが少ない最適化されていないアルゴリズムを使用する方がよい場合がよくあります。
あなたの例では、あなたが解決しようとしている問題に対してランタイム T'(N) = 10⋅N³ を持つ代替アルゴリズムがある場合、N=10 の場合は 10000 ステップしかかかりませんが、あなたの例では 150067 ステップが必要です。 . 基本的に、N ≤ 15の場合は T'(N) アルゴリズムが高速になり、 N > 15 の場合は T(N) アルゴリズムが高速になります。したがって、N > 15 が発生しないことが事前にわかっている場合は、理論的に効率の低いアルゴリズム T'(N) を選択することをお勧めします。
もちろん、実際には、次のような他の多くの考慮事項もあります。
T(n) は、サイズ n の入力にかかる時間を表す関数です。ビッグオー表記はその分類です。あなたの例で言ったように、その例の大部分はn ^ 2になります。
2 番目の質問については、big-oh 表記は、入力サイズが無限に近づくときに使用する必要があるアルゴリズムを示しています。実際には、補正するのに十分な大きさの入力が得られない場合があります。
たとえば、T1(n) = 999999999999*N および T2(n) = 2*N^2 の場合、最終的に n は、T2 が T1 より大きくなるのに十分な大きさになります。ただし、n のサイズが小さい場合、T1 は大きくなります。関数をグラフ化するか、連立方程式を解いて、n のサイズが違いを生むかどうかを調べることができます。
注: big-oh は複雑さの境界であることにも注意してください。これは、依然として正しい境界を緩くすることができることを意味します。
T(n) は単なる関数です。Oまたはビッグオーは、複雑さのレベルです。
T(n) は f(n) または g(n) のいずれかになります。
それが明確であることを願っています。
Big Oh は、アルゴリズムの時間または空間の複雑さの尺度です。
nの値が非常に大きい場合、高次の複雑さは>>低次の複雑さになるため、複雑さの低次を考慮しません。