4

私は反復アルゴリズムを持っています。反復ごとに計算量が徐々に減少します。これが私のアルゴリズムの図です：

Input size: nとTotal iteration = k

iter 1: time taken -> f1 * n
iter 2: time taken -> f2 * n
iter 3: time taken -> f3 * n
...
iter k: time taken -> fk * n

どこf1 > f2 > f3 >...> fkと0 <= f1, f2,...,fk <= 1

質問: このアルゴリズムの時間計算量は? それは...ですかBig-O(klog n)

Update:

質問があいまいだと思います。言葉で説明します：

私のアルゴリズムの入力は であり、繰り返しn実行します。kしかし、反復ごとに、入力サイズは の係数で減少しますunknown。削減にパターンはありません。

例:

iter 1: input size = n (always n)
iter 2: input size = n/2 (can change)
iter 3: input size = n/5 (can change)
iter 4: input size = n/8 (can change)
...
iter k: input size = n/10 (can change)
4

2 に答える 2

3

与えられた情報は十分ではありません。私たちが判断できるのは、複雑さが1であるということだけです。O((f1+ ... + fk)*n)

なんで？fiそれぞれが異なる複雑さを与える2つのケースの例を示します。

ケース1： fi = 1/2^i
この場合、を取得n * 1/2 + n* 1/4 + ... + n*1/2^k < nし、アルゴリズムは次のようになります。O(n)

ケース2： fi = 1/i
この場合、調和級数が得られます：n * 1/2 + n*1/3 + ... + n*1/k = n(1/2+1/3+...+1/k) = O(nlogk)

編集： あなたのコメントと編集に基づいて、アルゴリズムが説明されているように実行される最悪のケースは次のようです（私があなたを正しく理解している場合）：

iter1 -> n ops
iter2 -> n/2 ops
iter3 -> n/3 ops
...
iterk -> n/k ops

これが実際に当てはまる場合は、説明されているcase2と一致し、合計実行時間は調和級数：n + n/2 + n/3 + .. + n/k = n(1 + 1/2 + 1/3 + ... + 1/k)、ですO(nlogk)。

（1）厳密に数学的に言えば-大きなOは漸近的な上限であり、アルゴリズムはであるfi <= 1と推測できますが、例が示すように、厳密な境界ではありません-異なる値は異なる厳密な境界を与える可能性があります。O(nk)fi

于 2012-07-16T10:49:50.850 に答える
2

編集

すなわち：

あなたの例の分母が：

iter 1: input size = n (always n)
iter 2: input size = n/2 (can change)
iter 3: input size = n/5 (can change)
iter 4: input size = n/8 (can change)
...
iter k: input size = n/10 (can change)

厳密に整数である場合、それはO（n * log k）です。

これが理由です。シーケンスXnがO（Yn）であるためには、Xn <M * | Yn |となるような、実数のMと整数のmが存在する必要があります。すべてのn>mに対して。

ここで、シーケンスK = {1、1 / 2、1 / 3、... 1/k}について考えます。シーケンスN={1、2、3、4...}も考慮してください。

ここで、Yn = N ^ t * K（これはNとKの左外側の積です）とします。このシーケンスYnは、fiの値に関係なく、常にシーケンスよりも大きくなります。

したがって、Xn <1 * | Yn |です。ここで、Ynは調和級数にnを掛けたものです。amitが指摘したように、YnはO（n * log k）に分類されるため、Xnも分類されます。Xnを上に近づけることはできなかったので、Xnの最良の制限近似もO（n * log k）です。

于 2012-07-16T10:49:19.200 に答える