複雑さを判断する

Question

私はアルゴリズムXを与えたとしましょう。入力として整数が得られます。

今Xが小さく次いでx（x固定任意の自然数）であるすべての入力のn O（N ）工程のために必要と考えます。しかし、入力毎にn > xにはnステップかかる。

質問： Xの（最悪の場合）ランタイムの複雑さは何ですか？

回答： Xの実行時の複雑さ（最悪の場合）はO（n）です。すべての固定xについて、n>（x ）とn>（x ）のすべてのnの（最悪の場合）ランタイムがO（n）であるような数nを見つけることができます。私の答えが正しいかどうか分からない。

編集：分かりやすいようにT(n, x) \in if n <= x then O(n^2) else O(n)。最悪のランタイムの複雑さは何ですか？

Answer 1

O(n^2)n <= xのメンバー、O(n)の別段のメンバー、すなわちコスト関数（均一なコスト基準）T(n, x)とアルゴリズムXの実行時の複雑さ：我々は任意の数のようにx \in Natを修正する場合T(n, x) \in if n <= x then O(n^2) else O(n)は、ありますあなたは、O(n)と言う。

これはかつてxが固定されており、自然数は何の束縛を持っていないことを考えると、n >= x^2が常にあるので、アルゴリズムの漸近を扱うときに、それゆえ我々はO(n^2)を無視できる場合です。

したがって、R(n) = T(n, x) \in O(n)。

私はあなたの推論が妥当であると感じます。

Answer 2

Big-Oh（または任意の複雑さの境界）にとって重要なのは、ある一定の境界を超えるすべての値の振る舞いです。最終的にアルゴリズムはnで線形なので、ランタイムはO(n)にバインドされています。

アルゴリズムがnの入力を受け入れる場合、実際には何らかの番号システムでnという表現を受け入れているということです。典型的なコンピュータでは、これは2ビット（バイナリ）表現になります。ベースk（k-ary）表現は、切り上げられたlog_k（n）桁を取る。したがって、バイナリシステムで数が9の場合、表現は1001で、4ビット（ログベース2の9は3より大きいが2より小さいので4ビット）です。

これを考えると、あなたの入力サイズは、実際にnが、log_2(n)（バイナリと仮定した場合）ではないと、あなたのアルゴリズムは、時間n、ランタイムw.r.t.がかかる場合入力サイズは実際に指数関数的です（n = 2 ^（log_2 n）なので）。

これはマイナーなニックネックですが、アルゴリズムについて異なる考えをするかもしれません。番号を取る代わりにn要素を含むリストを取ると、その区別がなくなります。