0

SOでこの投稿を読んでいました：p-vs-np

そしてこれを見た：

"The creation of all permutations for a given range with the length n is not bounded, as you have n! different permutations. This means that the problem could be solved in n^(100) log n, which will take a very long time, but this is still considered fast."

誰かがどのように説明できますか？n^(100) log n で解ける

4

2 に答える 2

1

私はグーグルで調べたより長い説明から来るステートメントを注意深く読みました. 正しい表現は次のようになると思います。

「これは、問題が n 100 log n で解決できることを意味します。これには非常に長い時間がかかりますが、それでも高速であると考えられています。一方、TSP の最初のアルゴリズムの 1 つは O(n!) であり、別の1 つは O(n2 2n) でした。そして、多項式関数と比較して、これらは非常に速く成長します。」

「 the」ではなく「 a 」という言葉に注意してください。

于 2013-07-14T10:03:05.173 に答える
0

正しい近似は、スターリングの公式です。

それはあの人たちが書いたものと矛盾します。正直なところ、彼が何を意味していたのかはわかりません...

于 2013-07-14T09:47:26.833 に答える