是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
为什么算法时间复杂度没有三角函数级别？经过足够长的时间， AlphaGo 的棋谱能收敛到一张上吗？
类似微博的 feed 热度算法如何计算？
Matlab中的conv函数与卷积公式是什么关系呢？
李彦宏批评推荐式算法，你怎么看？
1/3+1/6=计算机是如何得出0.5的?
如何看待关于“数据结构与算法基础”的重要性？
刷完算法导论和leetcode，能找到什么水平的工作？
算法岗位真的需要顶会才能入场吗？
如何看待阿里 P8 加面 coding 环节，而 P7 却做不出头条算法题？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
如何看待软件工程师觉得学习算法没用？谷歌翻译这几个月的进化速度突然加快是什么原因？
nlp有哪些值得完整实现一遍的算法?
正负样本极不平衡的问题？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
李彦宏批评推荐式算法，你怎么看？
如何学习数据结构？
备战ACM，想问下有什么算法网课推荐吗?
算法书如何选择？
人工智能领域有哪些精妙的数学原理？
可以利用抄代码来同时记忆算法与练英文书法吗？
「贪心算法」的算法思路是什么，它存在什么缺陷？
PRML为何是机器学习的经典书籍中的经典？
刷完算法导论和leetcode，能找到什么水平的工作？
为什么说程序员要贷款买房之前最好先学好数据结构和算法？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
算法书如何选择？
计科和软工的区别？报哪个专业好些？
非CS背景，如何快速上手机器学习？
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
为什么梯度下降能找到最小值？
谁能最简单的详解椭圆曲线算法，secp256k1 是如何生成公钥和私钥的？
如何计算一局三国杀所进行的回合数的数学期望？
算法和算法策略是一个意思吗？
如何证明快速排序法的平均复杂度为 O(nlogn)？
刷完算法导论和leetcode，能找到什么水平的工作？
用 C# 写个方法解析简单的 JSON 字符串有哪些思路？
你写过哪些比较酷的十行以内的 Matlab 代码？
是否存在时间复杂度是O(tan N)的算法？
MD5哈希算法不可逆，但是网上有很多破译解密哈希密钥的网站，这些都是经过大数据堆积的吗？还是可以破解？