漸近複雜度

-3

假設計算機在微秒內執行一條指令，並且已知算法具有O（2^n）的複雜度，如果給該算法提供最多12小時的計算機時間，則確定最大可能可以使用該算法的n的值漸近複雜度

2010-09-20 Fiona

這沒有意義。 O（2^n）可能意味着只有2^n，但它也可能意味着1000000000 * 2^n。 – Henrik 2010-09-20 14:40:33

如果包括N的運行時間是4小時......如果在較短的運行時間內沒有較低順序的條件，則可以做出明智的決定。簡而言之，這個問題被打破*和*很難解決。 – dmckee 2010-09-20 14:43:47

這聽起來很像作業。另外，請使用標點和大寫。 – 2010-09-20 14:49:40

不可以。

O(2^n)意味着存在C使得limit n->infinity f(n)<=C*(2^n)。
但是這個C也可以是023945290378569237845692378456923847569283475635463463456的數量，所以即使是12小時也不能確保它即使在小輸入時也能運行。

來源

2010-09-20 14:44:56

因此，最小的可能值顯然是0. :) – Vatine 2010-09-20 14:50:28

@Vatine不一定，因爲只有極限可以保證，即使這可能需要14個小時。 – cobbal 2010-09-20 14:53:55

信息不足。一個O（2^n）的算法不一定需要大小爲n的輸入2^n步，它可能需要一個常數因子。事實上，它可能需要C *（2^n）+ B操作，其中C和B是常量（即它們不依賴於n），它們都是整數，並且C> = 1且B> = 0

來源

2010-09-20 14:51:25 ktho

那麼，由於O（2^n）是一個指數複雜度，你被要求提供「最大可能的指數」，所以你試圖找到一個N，所以2^N小於或等於12小時（* 3600秒，* 1000000微秒）。從那裏，你可以使用對數來找到正確的值，或者估計一個初始N並迭代，直到找到一個值。

來源

2010-09-20 14:51:26 Vatine

回答

相關問題