假设计算机在微秒内执行一条指令,并且已知算法具有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. Cassandra的“get_count”渐近时间复杂度
- 3. 渐近时间复杂度和折返
- 4. 算法复杂性渐近线图
- 5. 懒惰评估的渐近复杂性
- 6. 编译器的渐近复杂性
- 7. 如何找到3Sum.java的渐近复杂度
- 8. 是这个算法的渐近时间复杂度O(log n)?
- 9. 减少基于循环的代码的渐近时间复杂度
- 10. 对数与权力的渐近复杂性
- 11. T(n)的的渐近复杂= T(N-1)+ 1/N
- 12. 方案功能的渐近时间复杂性
- 13. Eratosthenes的筛接近复杂性近似
- 14. Kolmogorov复杂度
- 15. valarray复杂度
- 16. 渐近记法
- 17. 如何改变算法以获得更好的渐近复杂性?
- 18. 查找Java中排列的最有效方法[具有较低的渐近复杂度]
- 19. 真实世界哈斯克尔书 - 记录器monad示例的渐近复杂度
- 20. 时间复杂度
- 21. Android OnClickListener复杂度
- 22. 时间复杂度
- 23. 堆栈复杂度
- 24. stl list - 复杂度
- 25. 最近递归找到max的时间复杂度是多少
- 26. C++渐近分析
- 27. 如何计算复杂度?
- 28. 如何降低复杂度?
- 29. 时间复杂度(Java,Quicksort)
- 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