big-o - 面接の質問

Question

これはインタビューの質問です：

Given: f(n) = O(n)
       g(n) = O(n²)
find f(n) + g(n) and f(n)⋅g(n)?

この質問に対する答えは何でしょうか？

Answer 1

この回答が作成されたとき、f（n）はo（n）として示され、g（n）はΘ（n²）として示されました。

f（n）= o（n）およびg（n）=Θ（n²）から、f（n）+ g（n）に対してo（n²）の下限が得られますが、上限は得られません。 f（n）に上限が与えられていないため、f（n）+ g（n）になります。[上記では、Θは大きなθまたは大きなシータであることに注意してください]

f（n）・g（n）の場合、Θ（n²）はg（n）のo（n²）とO（n²）の下限と上限を意味するため、o（n³）の下限が得られます。ここでも、f（n）は任意に大きくなる可能性があるため、f（n）・g（n）の上限はありません。f（n）の場合、o（n）の下限しかありません。

f（n）= O（n）およびg（n）= O（n²）のように、fとgの上限のみを与えるように質問を変更すると、f（n）+ g（n）はO（ n²）およびf（n）・g（n）はO（n³）です。

これを厳密に示すのは少し面倒ですが、非常に簡単です。たとえば、f（n）・g（n）の場合、O（n）とO（n²）の定義により、n>X⇒C・n>となるようなC、X、K、Yが与えられると仮定します。 f（n）およびn>Y⇒K・n²> g（n）。J = C・KおよびZ = max（X、Y）とします。次に、n>Z⇒J・n³> f（n）・g（n）であり、f（n）・g（n）がO（n³）であることを証明します。

Answer 2

O(f(n) + g(n)) = O(max{f(n), g(n)}) 

だから最初に

f(n) + g(n) = O(max{n, n^2}) = O(n^2)

にとって

f(n) ⋅ g(n) 

私たちは

O(f(n) ⋅ g(n)) = O(n ⋅ n^2) = O(n^3)

Answer 3

このように考えてください。

f（n）= cn + d
g（n）= an ^ 2 + bn + p

次に、
f（n）+ g（n）= an ^ 2 +（nのより低い累乗）
そして、
f（n）.g（n）= xn ^ 3 +（nのより低い累乗）

したがって、O（f（n）+ g（n））= O（n ^ 2）

およびO（f（n）.g（n））= O（n ^ 3）

Answer 4

この質問はこのように理解することができます：-

f（n）= O（n）は、f（n）の計算にO（n）時間がかかることを意味します。

同様に、

O（n ^ 2）時間を必要とするg（n）の場合

それで、

P（n）= f（n）+ g（n）は間違いなくO（n）+ O（n ^ 2）+ O（1）を取ります（さらに、fとgの両方の値がわかれば）

。したがって、この新しい機能

P（n）にはO（n ^ 2）時間が必要です。

同じことが

Q（n）= f（n）* g（n）これにはO（n ^ 2）時間が必要です

。