アルゴリズムの時間複雑度がO(n^2)であるとします。 は今、私はここでアルゴリズムの時間複雑度を大きなオハイ表記で計算する
f(n) = O(g(n)) , if c1*g(n)<=f(n)<=c2*g(n) for all n>=n0
Constants c1 and c2 are positive real numbers
n0 = non negative integer
f(n),g(n) = non negative functions of non negative arguments
g(n) = n^2知っているとf(n) = n(n-1) .Iはc1 = 0 and c2 = 1を取るとします。
ので0*(n^2) <= n(n-1) <= 1(n^2)どこn>=1
しかし、条件はまた、n>=0
によって成立している。しかし、我々は、一般的にn = 0
だから私はn>=0を何を書くかを持っていませんOR あなたは文を読んでください
方法は次のとおりです。
機能f(n)特定の時点の後のfのn0すべての値（n）はグラムの周りの相対的な間隔（N）内にとどまる場合O(g(n))あり、間c1 * g（n）およびc2 * g（n）である。
したがって、n0、c1、およびc2が存在する限り、任意の関係についてこれを言うことができます。この理由から、n = 0は本当に問題ではありません。 n=1もありません。重要なことは、ある時点の後に条件が成立することです。条件が成立し、f（n）= n（n-1）がO（n^2）であると結論付けることを示すn0 = 42を取ることができます。
さらに複雑な関数の場合、f(n)は低い値に対しては妙に動作するため、無視してより高い値を選択すると意味があります。このような状態が見つかるかぎり、どれくらい大きいかにかかわらず、それは問題ありません。n0です。
これも分かりました。バイナリ検索の複雑さはO（log n）だという疑いがありました。 – user3126632
@ user3126632バイナリ検索はO（logn）です。ログベースは10です。バイナリサーチは実際にはログn（ベース2）で実行されますが、big-oに変換するとO（ログn /ログ2）がO（ログn）になります。 – intboolstring
@intboolstring繰り返しと再帰のアプローチで時間の複雑さは同じですか？ – user3126632
問題ではありません。必要に応じて 'n> = 12345'と書くことができます。不等式が成立する以上のいくつかの「n0」があることは重要です。 – interjay
'n0 =非負整数'、 'for all n> = n0'、' n0'は非負として定義されているので、 'n = 0'や何か否定で動作するかどうかは関係ありません。ここでは定義的に 'n> = 1'です。 –