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

@rogerchen Cheers ！本来我以为只有 1%的人能做对，结果还不到一百人回复呢，哈哈

@xuefei2062 大哥！我好想把你说的话对你再说一遍啊！

@xcatliu 你说的这个问题这是工程和科学的区别，工程上的局限性导致了所有数都是 32bit 这个固定规模。但是在图灵机模型下就没有这个限制啦~

@nagato 嘿嘿，这个词条也是很严谨的，说的是输入的“ size ”，而不是输入的“ value ”。对于一个 123456 这个数字，你说它的 size 和它的 value 能一样么？

@muziki 因为选项中没有正确答案，连出题人都不懂这个常识。估计绝大多数人也都不懂了吧，所以才拿出来和大家交流交流。

@ipwx 不敢当不敢当，我离科学还远着呢。我只是理解并搬运概念而已，还没厉害到制造概念的地步。

@lxiange 楼主正确
http://softwareengineering.stackexchange.com/questions/197374/what-is-the-time-complexity-of-the-algorithm-to-check-if-a-number-is-prime
判断一个数是否为质数和楼主的问题是相似的。这类问题的区别在于，问题的规模大小与数字本身的大小有关。

@zmj1316 但是他的失误是写的代码而不是用语言描述的

@yanwumo 但是他写的是代码，你们别被他绕进去了

因此，简单的判断质数的方法不能在多项式时间内完成。

@ipoh 是的，楼主的失误就在于他写成了代码，问题就变成用 int 实现时间复杂度是怎样了。

@rogerchen @lxiange 你们要说的事情我知道，但是呢……

根据你们的伪代码定义，令 k=log2(n)，那么 n++, i++, i<n 三个运算都 <= O(k)。一共进行了 n 次，那么 <= O(3kn) = O(3k*2^k) = O(3n log n)。

发现了没有，你们的第一个问题是混淆了 n 和 k 。这是我说你们民间科学家的第一个原因。

第二个原因，你们混淆了理论性（理想电脑）和工程性的边界。如果按照理论性来探讨，我们可以随时随地把某些操作定义为 O(1)。再说一遍， O(1) 的操作是定义出来的，我可以定义 i++, n++ 和 i<n 三个运算为 O(1)，这不违反理论。所以在理论性的前提下，这个函数为 O(n)。

如果按照工程性来考虑，这个世界上没有无线位宽的电脑。所以位宽 k 是常数。按照你们的代码风格为 C 来考虑，这个位宽可以定义为 k=32 。所以工程性为前提，算法复杂度为 O(3kn) = O(15n)。

混淆了理论性和工程性的边界，所以说你们是民间科学家。
- - - -

别拿什么考研答案来说事，我还看不上考研这个层次的题目。

@rogerchen 你提到 0-1 背包问题倒是给了我启发。

背包问题是已知的 NPC 问题，并且可以用各位 V 友眼中的“ O(n)时间”求解，
那我们已经证明 P=NP 咯~

没法再详细解释了，回复了那么多条还不能理解的，也就没必要去理解了，毕竟平时根本用不到这些概念。

各位自以为是的同学们请继续自以为是吧，因为我也会继续“自以为是”的：）

另外，撕逼时应该就事论事。不适合给对方扣帽子，也不要给自己戴高帽，说什么自己来自 985 、上过计算理论、熟读算法导论。也就和小白撕逼时这么做能增强说服力罢了。

@slfmessi 看见老熟人了，惭愧惭愧，今年报了名考研玩玩，还挺有意思的。
“标准答案”是根号 n 。

@lxiange 然而我还是不清楚你对一开始的代码所定义的复杂度是多少

运行时间和问题规模成线性关系, 这不就是小学生都懂的 O(n)吗

@ipoh
@yanwumo
嗯嗯，我确实错了。
严格说，单就这个代码而言，最坏时间复杂度应该是 o(1)，常数级，这个常数为 2^32 ，哈哈

@lxiange 好好看看人家 @ipwx 的解释，另外承认错误并不是什么丢脸的事，这么多人给你指出问题你还视而不见。。

@ipwx 我刚想码字刷新了下看到你的回复 我就不想码字了 给你个赞吧
这个讨论我认真看了下来，要不是花时间冷静下理了理，我还真觉得我三观被颠覆了——好吧，我承认本科时候没有认真学习，三观这么容易就被忽悠了

另外多说句看到这个回复
> @rogerchen Cheers ！本来我以为只有 1%的人能做对，结果还不到一百人回复呢，哈哈
你的回复已经在 81 楼了，题主你的概率论真的也得好好学学了，真心的，不然别人说你是民间科学家一点都不亏

高中生都能懂的 n, 在这各种偷换概念. 浪费时间

@ipwx 考研题是 while (sum < n) { sum += i++;}， 根本就不是他简化后的 for (int i = 0; i < n; i++) {bar++;}

@ivvei 难怪他说标准答案是根号 n

@ipwx 黑人问号？？？ 算法属于理论计算科学，和电脑，和工程有什么关系？
算法不认识任何实际计算机，只认识图灵机模型， RAM 计算模型。 1 至少用 1 个 bit ， 2^31 至少用 32 个 bit 很难理解么？

这让我想起当年，因为 int 是 32bit 的，所以所有算法都是常数时间的梗了。

@ipwx 我很清楚你在说什么，但是我很难在很短的篇幅内反驳你，所以暂且不表（看起来你部分同意我的观点，其实分歧更大）。

我承认，这种理论的问题用代码来表述是会引起歧义。
虽然大家可能都知道我在说什么，但是故意钻牛角尖我也只能认输。

@mcone 前面有人说我英语有问题，你说我概率论有问题。虽然你知道我当时在说一句玩笑话，但是你偏要矫枉过正，是不是要我算出置信区间来？

就事论事，别乱给人扣帽子，一定要在某给方面钻牛角尖打压对方以求精神胜利法的话，，，，，，那我也就认了。。。囧 rz

@rogerchen int 是 32bit 是怎么推出算法都是常数时间的

@ipoh 输入规模被框定了，比如 G(V, E)，最多有 2^31-1 个节点，最多有 2^31-1 条边。任何给定宽度的原始数据类型都面临这个问题，能够表达的数据规模是有限的。有限的就是常数时间。如果非要说 int 是 32 位的，楼主的算法时间复杂度是无穷大，因为输入的规模 32bit 没有变，运行时间发生了变化。

这种事情没什么好争的， 能插得上嘴的都知道双方纠结的点在哪。我只是觉得很多人嘲讽楼主不对，指数和线性的观点都有合理性。