来看看这个函数的时间复杂度是多少

所以答案就是 O(MAX_INT)?

楼主大发现！图灵奖非你莫属了

@rogerchen 楼主题目贴错了，按照你们的说法原题的答案就不是根号 n 了
所以这种常规问题并不是大家在钻牛角尖，非要不按照正常人的思路去考虑问题

@lxiange
导师就是计算理论的老师，计算理论不是算这个的，不要这样黑计算理论谢谢

http://imgur.com/a/Y29Qw

放张图吧，要是有人觉得 slide 作者也是民科我也没办法。

@rogerchen 这个其实也不一定哦，用定义一个数据结构不就可以解决这个问题吗？记得 K&R 里面就有写高精度数值的计算方式。简单的比喻就是像算盘一样，不够位拼一个啊。
不过既然是梗那就算了。

@menc

@neoblackcap 高精度也要撞到 32bit 的墙上，你数组最多有 2^32 个元素，其实就是 @lishunan246 的意思，在具体机器下讨论时间复杂度都是扯淡。时间复杂度就得在某种约定好的计算模型下来讨论。

@ipoh 代码只是对算法的描述，并不是算法本身。

我贴代码来描述问题，确实有可能会造成歧义
有意思的是，看前半部分评论。其实大家都知道我描述的算法是啥。重点在探讨 n 的定义，我还得费力去维基百科上复制粘贴。（好在现在大家貌似已经没有歧义了）
到后半部分评论，就强行去讨论现实计算机实现的问题。而计算复杂度问题，是算法自身性质，去讨论具体计算机内部的实现细节，其实已经跑偏了。

换个角度，我偏不认同“正常人”的思路，揪住这个问题不放，好像是我在钻牛角尖。

事实上我根本不 care 别人是否接受我的观点啊，我只是心平气和（嗯，应该还算心平气和吧）地和大家来探讨而已。

本来就是就事论事的讨论问题罢了，扣帽子或者冷嘲热讽没有任何意义。

@rogerchen 不用这么复杂，加法是 O(1)还是 O(n)

@lxiange 简单一点，回到考研原题吧，你觉得原题的算法复杂度是多少？你贴的题目和原题不一样

@menc 你要是说搞计算理论的人不会去研究这种无聊的问题我认可。
但是这个问题是可以划在计算理论范围内的：
https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E7%90%86%E8%AE%BA

> 计算模型
> 可计算性理论
> 计算复杂性理论

我们就事论事。没必要说自己的身份等等，对讨论没有帮助（有时说不定对自己还有反作用

伪多项式时间： https://zh.wikipedia.org/wiki/%E4%BC%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%97%B6%E9%97%B4

int n = 4;
n++;

这复杂度是 O(N) ?

@qwsqwa
less is more. 感谢回复！

其实“伪多项式时间”这几个字就能终结此帖了，之前 @rogerchen 也有提到。

竟然整出来这么多事儿。。。囧 rz

@lxiange 重要的不是“伪多项式时间”, 而是"则称其'时间复杂度' 为 '伪多项式时间' "

@rogerchen 那样不是可以定义一个数组来表示 2^32 位吗？当然所有的四则运算都要重新定义了，其实就是一个基于字符串存储的运算模型

第一次发现在程序员界也有民科。

@lxiange "竟然整出来这么多事儿"的原因是你有所求，如果你以疑问句的形式开这个贴，相信不会"这么多事"。你有装逼的所求，别人也有不让你装逼的意愿，这就是矛盾冲突所在。一句话，无欲则刚