Big-O表記を正しく理解していればk、アルゴリズムの効率化には一定の時間であるはずです。可変時間がかかることを考えると、なぜ一定時間ではO(1)なく一定時間が考慮されるのでしょうか? O(k)線形成長( O(n + k) )はこの変数を使用して、特定の時間だけ時間を右にシフトします。
質問する
6738 次
1 に答える
5
が定数O(n + k)であるような線形成長漸近線はありません。k定数であり、アルゴリズムの成長率の極限表現に戻った場合、定数は極限で脱落するためk、それがわかります。O(n + k) = O(n)
あなたの答えは、他の入力セットから基本的に独立している変数O(n + k)が原因である可能性があります。これは、並べ替えアルゴリズム分析の比較と移動でよく見られます。 kn
なぜ Big-O 記法を採用するのかというあなたの質問に答えるためにk(これは教育が不十分で、このすべての混乱につながっていると思います)、O() の 1 つの定義 (思い出したように) は次のとおりです。
Read: f(n) is in O( g(n) ) iff there exists d and n_0 where for all n > n_0,
f(n) <= d * g(n)
ここで、k が定数であり、したがって f(x) = k および g(x) = 1である問題に適用してみましょう。
- これらの要件を満たす
dとは存在しますか?n_0
自明なことですが、答えはもちろんイエスです。d > を選択kすると、n > 0 の場合、定義が保持されます。
于 2012-10-23T14:38:20.780 に答える