是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
为什么 360 面试官说 Trie 树没用？任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
C++笔试算法题允许用stl函数吗？
如何看待阿里 P8 加面 coding 环节，而 P7 却做不出头条算法题？
如何看待语音合成等 AI 算法、无人机等被列入限制出口技术目录？
为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？
有什么理论复杂但是实现简单的算法？
程序员能 20 分钟徒手写出一个没 bug 的 KMP 算法吗？（可以调试）
你见过哪些神一样的优化操作？
有没有可能让计算机去理解代码，从而写代码？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
如何判断这两份代码的时间复杂度？腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?
如果想大体地了解凸优化和非凸优化中比较重要的概念、理论知识和算法应该看哪些书籍或者论文？
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？
微信红包的随机算法是怎样实现的？
哪些看似与图论无关的问题可用图论模型解决？
如何系统地学习算法？
干支纪年法的算法是什么？
美团公开外卖订单分配算法，详解算法如何判断一个骑手的时间宽裕程度和顺路程度，有哪些值得关注的信息？
如何系统地学习算法？
算法岗位真的需要顶会才能入场吗？
学习算法有什么入门级的书 ? 或者学习资料。(英语不太好)
最快的 atoi、atof 实现是什么样的？
比特币的算法到底在算什么？
如何系统学习机器学习？
是否存在一个字符串，它的md5值是其自身？
到了 2022 年，人工智能有哪些真正可落地的应用？
只需4组数据，还原你的购物模式，具体算法是怎么实现的？
请问这个式子有没有简便算法（写法）？
如何看待「原谅宝」？
一个关于拓扑排序的扩展问题，可以做到的最优复杂度是？
Matlab中的conv函数与卷积公式是什么关系呢？
什么是递归？
刚进算法团队，大牛们讨论高深的cv术语和算法，如何才能听懂？
中国目前的人工智能在全球处于什么水平？
要是往马斯克嵌在猪脑袋里面的芯片里写进去“猪的生命也是命”。猪会不会不让人类吃他们的肉了呢？ ?
你们初刷leetcode时会怀疑自己的智商吗？
如何检验算法的正确性？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
比特币的算法到底在算什么？