是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
0基础开始,Leetcode200道题要多久左右?在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
计算机视觉（CV）的算法有哪些，具体都有哪些特点？
0基础开始,Leetcode200道题要多久左右?
为什么下面程序递归计算斐波那契数列java比c++要快？
如何统计拓扑排序的个数？
你为什么要学算法？
在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
李彦宏批评推荐式算法，你怎么看？
如何检验算法的正确性？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
怎么证明每个位上的数字之和可以被3整除的数可以被3整除？是否存在一个字符串，它的md5值是其自身？
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
Algorithmic Game Theory 和经济学中的 Game Theory 相似度大吗？
计算机开发岗和算法岗都有些什么区别？
机器学习里的 kernel 是指什么？
算法研究属于数学专业还是计算机专业？
我们高中数学为什么不重视算法？高中学的数列，三角函数，求导，圆锥曲线相关问题的解法和算法有什么关系？
在电子游戏中99%的暴击率、1%的爆伤和1%的暴击率、99%的爆伤，两者谁带来的收益更高？
量子计算机的出现会给实际生活带来怎样的改变？
蒙特卡罗算法是什么？
如何高效地获得玩家排名？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
学了四年算法，码了五万行代码，但是大一期末C语言模拟及不了格怎么办？
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？
这张图中能数出多少个三角形？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
你遇见过什么当时很有潜力但是最终没有流行的深度学习算法?
大公司笔试面试有哪些经典算法题目？
经过足够长的时间， AlphaGo 的棋谱能收敛到一张上吗？
什么是 hash？
学了四年算法，码了五万行代码，但是大一期末C语言模拟及不了格怎么办？
怎样将一个24的n次方复杂度的计算优化?
高斯模糊的原理是什么，怎样在界面中实现？
请问这个式子有没有简便算法（写法）？
最快的 atoi、atof 实现是什么样的？
有什么理论复杂但是实现简单的算法？
如何检验算法的正确性？