假設計算機在微秒內執行一條指令,並且已知算法具有O(2^n)的複雜度,如果給該算法提供最多12小時的計算機時間,則確定最大可能可以使用該算法的n的值漸近複雜度
Q
漸近複雜度
-3
A
回答
4
2
信息不足。一個O(2^n)的算法不一定需要大小爲n的輸入2^n步,它可能需要一個常數因子。事實上,它可能需要C *(2^n)+ B操作,其中C和B是常量(即它們不依賴於n),它們都是整數,並且C> = 1且B> = 0
1
那麼,由於O(2^n)是一個指數複雜度,你被要求提供「最大可能的指數」,所以你試圖找到一個N,所以2^N小於或等於12小時(* 3600秒,* 1000000微秒)。從那裏,你可以使用對數來找到正確的值,或者估計一個初始N並迭代,直到找到一個值。
相關問題
- 1. 漸近複雜度python
- 2. Matlab圖論漸近複雜度
- 3. Cassandra的「get_count」漸近時間複雜度
- 4. 漸近時間複雜度和折返
- 5. 復發關係和漸近複雜性
- 6. 漸進複雜度std :: remove_if
- 7. 算法複雜性漸近線圖
- 8. 編譯器的漸近複雜性
- 9. 懶惰評估的漸近複雜性
- 10. 算法的複雜性(漸近)
- 11. 是這個算法的漸近時間複雜度O(log n)?
- 12. 典型表達式的漸近複雜度
- 13. 如何找到3Sum.java的漸近複雜度
- 14. 以下時間複雜度漸近地相同嗎?
- 15. log_2(n)-log_3(n)的漸近複雜度是多少?
- 16. 時間複雜度最小漸近運行時間
- 17. 這個僞代碼的漸近複雜度是什麼?
- 18. 構建二叉樹的漸近複雜度
- 19. 下面這段代碼的漸近時間複雜度是多少?
- 20. 減少基於循環的代碼的漸近時間複雜度
- 21. 方案功能的漸近時間複雜性
- 22. 對數與權力的漸近複雜性
- 23. T(n)的的漸近複雜= T(N-1)+ 1/N
- 24. Eratosthenes的篩接近複雜性近似
- 25. Elasticsearch複雜鄰近查詢
- 26. `append`複雜度
- 27. Kolmogorov複雜度
- 28. valarray複雜度
- 29. 時間複雜度和空間複雜度,如何計算空間複雜度
- 30. 漸近記法
這沒有意義。 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