是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
如果有人想走遍中国所有的省级行政区（含港澳台），总路程最小可以是多长？什么是递归？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
学了四年算法，码了五万行代码，但是大一期末C语言模拟及不了格怎么办？
如何评价 2021 年 ICPC 银川赛区？
nlp有哪些值得完整实现一遍的算法?
任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
计科和软工的区别？报哪个专业好些？
平滑的战争迷雾效果是如何实现的？
普通人如何对抗算法，从而避免信息茧房？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
C++中开多个数组和用struct封装起来哪个速度更快？有哪些解决完之后让你拍案叫绝的算法问题？
苹果的 Differential Privacy 差分隐私技术是什么原理？
逃离丧尸包围的游戏，你能否逃生？
经过足够长的时间， AlphaGo 的棋谱能收敛到一张上吗？
「贪心算法」的算法思路是什么，它存在什么缺陷？
机器学习里的 kernel 是指什么？
请教拓扑排序中的一点疑问？
将并行计算纳入算法竞赛，是否合适？
cpp是不是最方便研究算法的语言？
红黑树的实现可以有多精简（各种语言随意）？
如何理解算法时间复杂度的表示法，例如 O(n²)、O(n)、O(1)、O(nlogn) 等？
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？
Java对于int变量a，如何以最快速度计算34*a?
std::list::sort 用了什么算法？为什么速度这么快？
负数与负数相乘为什么会得正？
如何看待三星Galaxy note10 5G DxO摄像头评测得分113分超华为P30 Pro？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
如何看待三星Galaxy note10 5G DxO摄像头评测得分113分超华为P30 Pro？
机器学习到底是什么，如何使用这项技术？
程序员必须掌握哪些算法？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
算法研究属于数学专业还是计算机专业？
人工智能领域有哪些精妙的数学原理？
请教拓扑排序中的一点疑问？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
为什么技术主管跟我说程序员学算法不是最重要的，从工作项目中学习实际才是最重要的？
为什么现在有这么多人工智能无用论？
如何利用群论的知识解决三阶魔方？