是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
对于编程思想和能力有重大提升的书有哪些?有哪些解决完之后让你拍案叫绝的算法问题？
如何看待网传字节跳动 28 岁图像算法工程师心梗猝死？还有 30 年房贷没还完，可以退房退款吗？
哪位大佬能给我详细解答下AHP灰色综合评价模型的原理和算法啊，不胜感激！？
如何评价 2021 年 ICPC 银川赛区？
腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?
要是往马斯克嵌在猪脑袋里面的芯片里写进去“猪的生命也是命”。猪会不会不让人类吃他们的肉了呢？ ?
二分查找有几种写法？它们的区别是什么？
算法工程师的落地能力具体指的是什么？
QR 二维码在不影响扫码的情况下，哪些部分可以删除？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
如何看待字节跳动算法工程师猝死，妻子怀孕两个月？当前情况如何？Algorithmic Game Theory 和经济学中的 Game Theory 相似度大吗？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
计算机开发岗和算法岗都有些什么区别？
计算机开发岗和算法岗都有些什么区别？
如何证明快速排序法的平均复杂度为 O(nlogn)？
蒙特卡罗算法是什么？
参加ICPC国际编程竞赛的大学生到底有多厉害，在校生该如何准备？
类似微博的 feed 热度算法如何计算？
面试题:一个长度为n的数组，其中数组中每个元素的值都不大于n，如何用O(n)的算法判断数组中是否存在重复元素?
如何统计拓扑排序的个数？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
能否通过计算机找到适合速拧的魔方解法？
什么是 hash？
如何证明快速排序法的平均复杂度为 O(nlogn)？
一个算法面试题，怎么写？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
参加ICPC国际编程竞赛的大学生到底有多厉害，在校生该如何准备？
一道程序员面试题？
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？
高斯模糊的原理是什么，怎样在界面中实现？
如何通俗地讲解 viterbi 算法？
如何学习视频识别技术？
世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？
从一读到一亿需要读多少个汉字？
什么才算是真正的编程能力？
如何看待三星Galaxy note10 5G DxO摄像头评测得分113分超华为P30 Pro？
怎么证明每个位上的数字之和可以被3整除的数可以被3整除？