0

私は、コードから大きな記法を作成することに頭を悩ませています。

基本的な手順を理解しています

for (int i = 0; i < n; i++)O(n)になります

そしてそれ

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) 

O(n 2 )になります

対数値を計算する場所または方法を理解するのに苦労しています。

すなわち

だろう:

for (int i = 0; i < n * 2; i++)O( log n)またはO(n log n)またはO(log 2n)など

例と表記法がどのように形成されたかについて、誰かがコード形式で示してください。

私は調査し、並べ替えが関係し、リストが切り刻まれているなどの例を取得し続けています。これはフォームでは意味がありますが、上記のコードにそれを適用する方法がわかりません。

私はコーディング全体とビッグオー記法に不慣れです。

オブジェクト、クラス、ループ、関数、構造体などに精通しています。コースの一部であるため、C++ の学習に忙しくしています。私の教科書では、対数のbig-o計算についてはあまりよく説明されていないか、まったく説明されていません。

4

1 に答える 1

1

コードを再帰関係として表すことができます。

T(n) = T(n-1) + 2 * c, where c = the inner part of the code

私たちは何2 * n回もやります。

次のようなソリューションを提供します。 T(n) = 2 c n + c_1, where c_1 a constant

そして、2 * cは定数であり、第 2 項も定数が低下するため、次のように書くことができます。

O(n)

于 2017-03-28T21:41:48.907 に答える