是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌 ）是怎样的？是否存在仅由1和2组成的长度为2^n的序列，可以做到在这个序列中取出所有含1和2的长度为n的序列？
在机器学习模型的训练期间，大概几十分钟到几小时不等，大家都会在等实验的时候做什么？
最快的 atoi、atof 实现是什么样的？
中国目前的人工智能在全球处于什么水平？
怎样衡量一个机器学习工程师对算法的掌握程度？
学物理为什么会觉得计算机很难？
只需4组数据，还原你的购物模式，具体算法是怎么实现的？
美剧《硅谷》第三季第一集神秘代码写的是什么？
数据结构与算法中，树一般会应用在哪些方面？为什么？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
什么是机器学习？开发一个 App，利用 Bose 降噪耳机的原理实现其功能？
有什么在线的编程游戏？
刚进算法团队，大牛们讨论高深的 cv 术语和算法，如何才能听懂？
「贪心算法」的算法思路是什么，它存在什么缺陷？
学物理为什么会觉得计算机很难？
参加 ACM-ICPC World Final 是怎样一种体验？
计科和软工的区别？报哪个专业好些？
一堆n维空间的由m个点组成的点集，m大于n，我们只知道它们之间的距离，能否判断所在空间的维数？
假如我知道了抽卡游戏的随机数生成算法源码，是否能成为欧皇？
为什么梯度下降能找到最小值？
什么才算是真正的编程能力？
我发现设计模式一个很奇妙的情况，不知各位知友遇过没？
算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
哪些开发会用到微积分、离散数学、线性代数、概率论的知识？
是否存在一个字符串，它的md5值是其自身？
什么是 hash？
计算器或计算机如何进行比较复杂的数学计算？
失传的缀数法最有可能是什么方法？
为什么在数学中，一些运算的逆运算比原运算难很多？
红黑树的实现可以有多精简（各种语言随意）？
如何看待三星Galaxy note10 5G DxO摄像头评测得分113分超华为P30 Pro？
如何高效地获得玩家排名？
可以利用抄代码来同时记忆算法与练英文书法吗？
有没有可能让计算机去理解代码，从而写代码？
一个程序员的水平能差到什么程度?
Java对于int变量a，如何以最快速度计算34*a?
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？
如何高效地获得玩家排名？