0

C を長さ n のビット文字列を {0, 1, 2} の要素にマップする回路とする。巨大なループで長さ n のビット文字列のセットを並べ替えると想像してください。00000 は 00001 と 11111 に隣接しています。00001 は 00000 と 00010 に隣接しています。等

C(00000) = x かつ C(00001) != x の場合、C はこれらの隣接ノード間で値を変更しました。C がループで値を変更した合計回数をカウントしたい。より具体的には、この数が偶数か奇数かを知りたいだけです。

この問題の複雑さは何ですか?

4

1 に答える 1

0

関数 (cuircuit) C に関する追加情報がない場合は、数える必要があると思います... (確かにできないことは、適切な入出力のみを見て、C の機能的な「特性」を推測することです。考慮のドメインのサブセット。)

したがって、O(n) の C の多くのアプリケーションを実行する必要があると思います。ここで、n は「ループ」のサイズです...したがって、あなたの場合は指数関数的です

于 2013-04-25T10:56:38.880 に答える