是否存在时间复杂度是O(tan N)的算法？ 第1页
1
rushcheyo-56 网友的相关建议:
这是一个比较无聊的问题。在复杂性理论里（例如 Time Hierarchy Theorem 中），为了避免过于病态的函数，我们考虑的图灵机的运行时间 都是所谓的 time-constructible function，即满足以下条件：
- ；
- 存在图灵机 ，以 为输入时，会在至多 时间内输出 的二进制表示。
这样的要求是因为我们经常要模拟一个运行时间 的图灵机指定的步数，我们肯定希望这样操作的运行时间是 的，但是如果计算出 的时间都不止 那就肯定不行了。本题中的 显然不符合这样的要求。另外就算换一个计算模型，在相应的 time-constructible function 定义下也是做不到的。
hqythu 网友的相关建议:
这个事情是不讲道理的，我来这里说道说道。
注意到这里说的是 而不是 或者 之类的。回顾一下大O渐进记号的定义：
注意到由于有绝对值，所以 为负数好像也没啥关系。
考虑到一个合理的算法至少拥有不低于某常数的运行时间， 。
而 是周期函数，在接近 的时候值趋近于0。因为 可以任意大，这样就显然不存在一个 使得对任意充分大的 都有 ，因为 可以任意小。
即使限制 只能为正整数 ，也可以知道，由于有理数可以逼近无理数，那么 ，同样可以使得 任意趋近0。
如果考虑的是 的话，这个就变得不一样。因为 是无界的，而且 记号同时限制了上下界，这这个仿佛是在说，算法的运行时间随着问题规模忽大忽小的变化，听起来也不是很讲道理。
而那个加1一直加到小于 的最大整数，这个 实在不算是个问题规模的描述。
因为函数的渐进性质刻画的是当函数自变量充分大的时候的变化趋势，在周期函数上讨论渐进性质实在是一件很没有意义的事情。
Reference：
1
相关话题
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？如何学习视频识别技术？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
如何评价姜新文老师提出的NP=P这篇文章？
如何看待2021年秋招算法岗灰飞烟灭？
什么是机器学习？
构建进化树的意义是什么？除了看亲缘关系之外。
如果想大体地了解凸优化和非凸优化中比较重要的概念、理论知识和算法应该看哪些书籍或者论文？
电子设备（如电脑）内置时钟的算法是如何“分辨/度量”出一秒的长度的？
你们初刷leetcode时会怀疑自己的智商吗？
前一个讨论
剑桥本科申请如何规划？具体流程是怎样的？
下一个讨论
长期当程序员会失去什么？
相关的话题
一道程序员面试题？有哪些「上帝算法」？
2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位...如何解答呢？
Matlab中的conv函数与卷积公式是什么关系呢？
能否使用神经网络来判断奇偶数？
学了四年算法，码了五万行代码，但是大一期末C语言模拟及不了格怎么办？
数字图像处理的工作是用传统算法更多还是用深度学习更多?
如何生成多个互不重叠的不同半径圆？
算法老师劝学生放弃学习 JavaScript，我该怎么办？
非计算机专业，想刷leetcode，请问在此之前需要做什么准备？
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？
哪些开发会用到微积分、离散数学、线性代数、概率论的知识？
如何高效地获得玩家排名？
如何评价各种关联因素分析算法,尤其是在算法效果对比方面?
你写过哪些比较酷的十行以内的 Matlab 代码？
数字图像处理的工作是用传统算法更多还是用深度学习更多?
Java对于int变量a，如何以最快速度计算34*a?
有哪些数学定理或者数学知识惊呆了你？
100个金币，只有1个略重，其余99个一样重。给你一个天平，最少称几次能确保找出那个略重的?
为什么梯度下降能找到最小值？
为什么下面程序递归计算斐波那契数列java比c++要快？
在一个非常繁忙的十字路口，红绿灯坏了，请问无人驾驶汽车能顺利通过吗？
哪段代码最能代表程序员的暴力美学？
一个算法面试题，怎么写？
如何证明一个数 n 的因子之和是 O(n) 的？
计算机开发岗和算法岗都有些什么区别？
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
感觉算法在程序员中快被吹上天了，如果只是搞编程的话，是不是没必要死磕算法？
军事级加密算法有哪些？