4
A
回答
0
我不知道你说“渐近近似”的意思,但在理论上,它很容易建造这种“算法” ......
var l = non_monotonic_function(input.size);
for (var i = 0; i < l; ++ i)
do_some_O1_stuff(i);
0
我不认为有很多(任何)真正的算法是这样的,但就在我的头顶,在伪代码:当n趋于无穷
void non_monotonic_function(int n)
{
System.wait(Math.sin(n));
}
这种算法是不渐进。
2
想到离散傅里叶变换;如果它被施加如下这将是非单调(和不连续的):
if is_power_of_2(len(data)):
return fft(data)
return dft(data)
因为为O DFT运行(N ** 2)和FFT运行在O(N日志N)。设计一个算法,人们可能会找到一种方法来填充输入数据以消除非单调行为(即加速较小的输入),就像通常用fft所做的那样。
相关问题
- 1. 算法复杂度时间
- 2. 算法算法的时间复杂度
- 3. 算法时间复杂度算例
- 4. 算法复查时间复杂度
- 5. 简单的时间复杂度计算
- 6. 计算时间复杂度
- 7. 时间计算复杂度?
- 8. 计算时间复杂度
- 9. 计算时间复杂度
- 10. 时间复杂度和空间复杂度,如何计算空间复杂度
- 11. 递归算法的时间复杂度
- 12. 算法的时间复杂度
- 13. 算法的时间复杂度分析
- 14. 以下算法的时间复杂度?
- 15. 以下算法的时间复杂度
- 16. 二次算法的时间复杂度
- 17. 时间复杂度低于gcd算法
- 18. 分析时间复杂度的算法
- 19. 排序算法的时间复杂度
- 20. 算法的BigO时间复杂度
- 21. 算法的时间复杂度
- 22. 解析算法的时间复杂度
- 23. KMP算法的时间复杂度
- 24. kd-tree BBF算法时间复杂度
- 25. 算法的时间复杂度分析
- 26. 算法的时间复杂度
- 27. Fleury算法的时间复杂度
- 28. 计算函数的空间复杂度和时间复杂度
- 29. 安德鲁算法(复杂船体)的时间复杂度
- 30. 算法分析算法时间复杂度
我认为这将是O(1) – ThomasMcLeod 2011-02-03 23:20:03
或更确切地说,theta(1) – ThomasMcLeod 2011-02-03 23:20:49
是的,我猜你的正确。它由一个常数函数定义在上面和下面。 – 2011-02-03 23:24:41