これがこれを尋ねるのに適切な場所かどうかはわかりません。Cormen page 1056 で、アルゴリズムの実行時間が O(k) で、「k」が単項、つまり k 1 の文字列で表される場合、アルゴリズムの実行時間は 0(n) であり、「n」は入力サイズはビット単位で、"k" が 2 進数で表される場合、n=lg k+1 として、アルゴリズムの実行時間は o(2^n) になります。
したがって、この場合、他の場合の指数関数とは対照的に多項式時間を与えるため、「単項」表現が好まれない理由は疑問です。
2655 次
1 に答える
6
単項時間は、入力サイズに相対的な多項式時間を与えますが、実際の実行時間は、使用される表現に関係なく同じです。
問題は、複雑さが入力の関数として計算されることです。単項表現を使用する場合、実行時間を変更せずに入力のサイズを増やします。
単項ベースで表すにはビットkが必要なので、入力のサイズが線形であるためです。ただし、同じソリューションの場合、を表すビットが必要なため、バイナリ表現を使用すると、 になります。nO(k)O(n)O(k) = O(2^logk) = O(2^n)logkk
あなたが説明していることは、動的ポログラミングを使用したナップザックソリューションなどの疑似多項式時間アルゴリズムに密接に関連しています。O(W*n)W
于 2012-05-02T21:35:48.463 に答える