algorithm - 大きなO表記の合計

Question

重複の可能性：
異なるルーチンを一緒に追加するときの大きなO

何にO(n) + O(log(n))還元されますか？私の推測ではO(n)、厳密な推論を与えることはできません。

は定数なので、O(n) + O(1)に減らす必要があることを理解しています。O(n)O(1)

Answer 1

まあ、私たちは単にそのようなものO( f(n) ) + O( g(n) ) = O ( f(n) + g(n) )を計算しようとしているのでf(n)f(n) > n + log(n)

nが十分log(n) < nに成長するにつれて、次のように言うことができます。f(n) > 2n > n + log(n)

したがってO(f(n)) = O(2n) = O(n)

より一般的な意味では、ある定数のO( f(n) ) + O( g(n) ) = O( f(n) )場合c*f(n)>g(n)c。なんで？この場合f(n)、アルゴリズムを「支配」し、時間計算量を決定するためです。

Answer 2

注文は常に上位の条件に削減されます。私はあなたに直感的な推論を与えることができます。あなたが持っているとしましょうO(n + n^2)。では、実行時にどの部分がより重要な役割を果たすでしょうか？nまたはn^2。明らかにn^2。n ^ 2がある場合、nを増減してもnの影響に気付かないためです。

例として、

let n = 100, then n^2 = 10000
means n is 0.99% and n^2 is 99.01% of total running time.
What would you consider for runtime?
if n is increased then this difference is clearer.

あなたは今理解していると思います、

Answer 3

答えはO（n）です。O（log n）はO（n）よりも小さいです。したがって、それらの加算は、O（n）である最大値を合計します。