是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
机器学习小白来提问：关于联邦学习FedAVG和FedSGD的问题？哪些开发会用到微积分、离散数学、线性代数、概率论的知识？
程序员能 20 分钟徒手写出一个没 bug 的 KMP 算法吗？（可以调试）
如何直观地解释 backpropagation 算法？
机器学习的算法和普通《算法导论》里的算法有什么本质上的异同？
怎样衡量一个机器学习工程师对算法的掌握程度？
能否详细说明一下对称算法中的DES,AES?
能否通过计算机找到适合速拧的魔方解法？
如何评价一线大厂资深 APP 性能优化系列之异步优化与拓扑排序？
为什么有些算法工程师从来不谈业务，不谈解决问题，不谈价值挖掘，开口闭口就是算法模型，炼丹调参工程化？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra?cpp是不是最方便研究算法的语言？
你见过哪些神一样的优化操作？
要是往马斯克嵌在猪脑袋里面的芯片里写进去“猪的生命也是命”。猪会不会不让人类吃他们的肉了呢？ ?
为什么技术主管跟我说程序员学算法不是最重要的，从工作项目中学习实际才是最重要的？
如何面对算法竞赛的焦虑？
我们高中数学为什么不重视算法？高中学的数列，三角函数，求导，圆锥曲线相关问题的解法和算法有什么关系？
推荐系统有什么危害?
DeepMind 再登 Nature，用 AI 破译古希腊文字，该成果会对人类历史研究带来什么影响？
怎样将一个24的n次方复杂度的计算优化?
如何看待语音合成等 AI 算法、无人机等被列入限制出口技术目录？
c++怎么在1到n这些数中随机产生k（k<n）个？当然，k个数互不相等。有什么比较好的写法吗？
c++怎么在1到n这些数中随机产生k（k<n）个？当然，k个数互不相等。有什么比较好的写法吗？
2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位...如何解答呢？
红黑树的实现可以有多精简（各种语言随意）？
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？
为什么 Google 翻译只重算法不重语言学的语法结构和规则？
c++怎么在1到n这些数中随机产生k（k<n）个？当然，k个数互不相等。有什么比较好的写法吗？
链表求交集，从链表头删去一长串而非一个节点？（已解决）?
程序员必须掌握哪些算法？
算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
在一段高速公路上，30分钟之内见到汽车经过的概率是95%，那么，在10分钟内见到汽车经过的概率是多少？
如何系统地学习算法？
如何通俗地讲解 viterbi 算法？
网上常能见到的一段 JS 随机数生成算法如下，为什么用 9301, 49297, 233280 这三个数字做基数？
腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?
为什么算法时间复杂度没有三角函数级别？
有什么在线的编程游戏？
利用无理数压缩数据是否可行？
如何高效地获得玩家排名？