Sub Exponential Compleixty

2015-04-02 57 views -1 likes

-1

我在下面的鏈接中看到，2 ^{n ^O（1）} 是次指數複雜度。我不明白2 ⁿ和2 ^{n ^O（1）}之間的差別。它們與O（1）的計算結果是否相同？Sub Exponential Compleixty

我已經在因此具有O（2 ^Ñ）複雜2 ^Ñ -1運行時步驟已經解決了子集和問題的算法。那是次多項式時間嗎？如果它是違反指數時間假設（ETH）並證明P不等於NP！

我也知道這種問題的蠻力運行在O（2 ⁿ）。那麼這個複雜度和次指數的區別是什麼？

請幫忙。謝謝！

2015-04-02 vinaych

我看到有關鏈接的內容嗎？ – ChiefTwoPencils 2015-04-02 02:55:33

該鏈接使用小o，而不是大o。 – 2015-04-02 04:53:04

回答

O（1）絕對不是一樣1.

如果F（X）是在O（1）的，那麼G（X）=Ç × ˚F （x）。例如，F（X） =（X − 1）⁄ X顯然是O（1），因爲它的漸近爲1，所以是G（X） =（X − 1 ）＆thinsp; ⁄＆thinsp; 2＆thinsp; x，其漸近線爲0.5。

但2 ^Ñ（= 2 ^Ñ）爲2 ^Ñ（= 2 ^√Ñ）完全不同。後者當然可以被描述爲次指數。

2015-04-02 04:46:29 rici

相關問題