是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
比特币的算法到底在算什么？如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明?
如何看待淘宝、微信、抖音推出算法关闭键？会带来哪些影响？还有哪些问题值得关注？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
如何看待字节跳动算法工程师猝死，妻子怀孕两个月？当前情况如何？
链表求交集，从链表头删去一长串而非一个节点？（已解决）?
如何系统地学习算法？
怎么证明每个位上的数字之和可以被3整除的数可以被3整除？
比特币的算法到底在算什么？
智能座舱的算法包括哪些方面？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
计科和软工的区别？报哪个专业好些？机器学习小白来提问：关于联邦学习FedAVG和FedSGD的问题？
Apriori算法是什么？适用于什么情境？
腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
Algorithmic Game Theory 和经济学中的 Game Theory 相似度大吗？
腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?
人工智能领域有哪些精妙的数学原理？
如何理解计算物理中的元胞链接列表（Cell Linked List）算法？
只需4组数据，还原你的购物模式，具体算法是怎么实现的？
如何通俗地讲解 viterbi 算法？
能否通过计算机找到适合速拧的魔方解法？
请教拓扑排序中的一点疑问？
如何评价各种关联因素分析算法,尤其是在算法效果对比方面?
推荐系统有什么危害?
美剧《硅谷》第三季第一集神秘代码写的是什么？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
PRML为何是机器学习的经典书籍中的经典？
利用无理数压缩数据是否可行？
如何看待 2022 年秋招算法岗人间地狱？
如何看待 2022 年秋招算法岗人间地狱？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
正负样本极不平衡的问题？
在Auto ML的冲击下，ML算法人员是否会在前者成熟后失业的情况？
要是往马斯克嵌在猪脑袋里面的芯片里写进去“猪的生命也是命”。猪会不会不让人类吃他们的肉了呢？ ?
能否通过计算机找到适合速拧的魔方解法？
如何利用群论的知识解决三阶魔方？
有什么算法可以很快的找出所有完全对称日呢?
你写过哪些比较酷的十行以内的 Matlab 代码？
一道程序员面试题？