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

@lxiange 明白了，自己大意把问题想随便了，之前没好好说话，抱歉

@neoblackcap
如果我偏要和你钻牛角尖，我可以说一个字符串最长也就 4G 啊（ 32 位机器上），依然是有限的（即使你把全人类可用的内存都用上，那也是有限的内存）。无论你设计什么数据结构，只要在现实中实现，那一定是有限的位数，那么它的最坏时间复杂度，就是最坏情况下需要的那个时间——那个常数。所以依然是常数时间。

ok ，假设不讨论内存有限的问题，完全按照你描述的理想情况，那你其实就是在模拟一个图灵机咯！你是在佐证我的观点。
事实上，讨论算法计算时间复杂度，就不应该去管实际实现上的种种限制，而单就这个模型去思考。

@lxiange
显然事实就是这样，但是有限并不是因为 32bit 的限制,有限是因为现实资源有限。
我是没想到这个梗居然还可以佐证你的观点。

@lxiange 你错了，我们现在一般考虑算法时间复杂度（包括你的考研题目）都是有限制的，有前提条件的。单纯这个题目而言根本涉及不到你那么多所谓的概念，用这个来装就显得幼稚了。

楼主是正确的，贴一篇 so 回答希望能帮助各位理解
http://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time

@lxiange 考研题是这个 while (sum < n) { sum += i++;}

@jsq2627 那加法就不是 O(1)咯？

我试着解释一下
平时我们说的时间复杂度“ O(关于 n 的一个表达式)”里面 n 的定义是这样的：
The size of the input to a problem is the number of bits required to write out that input.
而此考研题目的精妙之处在于混淆输入数值 n 和上述输入尺寸 n 的概念。

假设把题目那个函数里面的 n 都替换成 x 作为变量名。
x=2^n （ n 是 x 的二进制位数）
于是时间复杂度为 O(x)即 O(2^n)

@jsq2627 考研题是这个 while (sum < n) { sum += i++;} 不是楼主贴的
而答案是 根号 n
你再想想

@qwsqwa
@lxiange 然而『伪多项式时间』（ https://zh.wikipedia.org/wiki/%E4%BC%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%97%B6%E9%97%B4 ）中的例子似乎无法说明你们的观点。

在素性测试中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数 N ，使用从最小的素数 2 开始，到 N {\displaystyle {\sqrt {N}}} \sqrt{N}为止的整数依次对 N 进行试除，如果均无法整除 N ，则 N 是素数，这个过程需要进行至多约 N {\displaystyle {\sqrt {N}}} \sqrt{N}次整数除法，即其时间复杂度为 O ( N ) {\displaystyle O({\sqrt {N}})} O({\sqrt {N}})，为 N 的多项式。令 D 为 N 的二进制表示的位数，那么 N 可以表示为以 2 为底 D 的幂，因此素性测试问题的时间复杂度用 D 表示应为 O ( 2 D / 2 ) {\displaystyle O(2^{D/2})} O(2^{{D/2}})。因此，上述算法是一个伪多项式时间算法。

在这例子中针对 N 和 D 这两个不同的定义，给出了两个不同的时间复杂度的结果。

@jsq2627 他连题目都给人偷换了，还讨论什么。考研出题的人就是正常思路的人，原题就是根号 N ，因为步进不断变大。而他所谓的“简化”，简化成了 O(n)的，还各种偷换概念狡辩……

这个不管是怎样的，你都不能说 O(n)是错的，如果 n == variable in the input

他的时间复杂度不管怎么算，最会都会等于 O(2^m) = O(n)。

就顶楼那个例子，我还想延伸一步
```
void foo(int[] arr) {
int bar = 0;
for (int i = 0; i < arr.length; i++) {
bar++;
}
}
```

这个例子时间复杂度又是多少呢？

又或者按照我在#130 楼里所指出的那样，如果我的回答是『对于给定的正整数 n ，它的时间复杂度为 O(n)』，这样子的回答是否正确呢？

@jhdxr 时间复杂度特指后者用 D 表示的形式。 wiki 上语言表达有些不严谨，前者 O(根号 n)不能称为“时间复杂度”，只能叫做运行时间与 n 的关系。 wiki 后面特别强调“因此素性测试问题的时间复杂度用 D 表示应为 {\displaystyle O(2^{D/2})} O(2^{{D/2}})”。我想也许是翻译导致这个不严谨的产生。（不过英文原文我并没有找到同样的解释）

金币赚得好开心

@linboki 好吧，就按你对装逼的定义，我是在装逼。那你看我这次装逼还成功不 :P

@ipoh @reus @jsq2627 请看 13 楼，我订正过了。
4 楼的代码是我临时直接手写的，并且 v2 不能编辑，所以非常不好意思。

不过其实没有大的影响，
while (sum < n) { sum += i++;}
和
for (int i = 0; i < n; i++) {bar++;}
在时间复杂度上都是一样的。
(根号 2)^n 和 2^n ，以及 10^n ，没有本质区别。

（虽然在错误的理解下，一个是 O(n)，一个是 O(根号 n)）

此外，@ipoh 在 124 楼的回复。
计算复杂性理论只是讨论算法的，绝对不应该去考虑现实限制的（当然工程师都一定忍不住去考虑）。

因为讨论的是算法的理论性质，和具体计算机无关，摘自维基：
“计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源，
....计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。”
喏，不能本末倒置啊，讨论计算复杂性时，是不需要考虑限制的。

并且就算有实际限制，也和是 O(n)还是 O(2^n)无关的啊。
这是不小心引出的另一个话题，限制 32bit 的话，那就都变成 O(1)了。


@jhdxr 所以，为什么叫作“伪”多项式时间？
里面不是有这句话么：
“因此素性测试问题的时间复杂度用 D 表示应为 O ( 2 D / 2 ) {\displaystyle O(2^{D/2})} O(2^{{D/2}})”


@reus
@jedihy
https://en.wikipedia.org/wiki/Time_complexity

“ In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.”

看看我有木有偷换概念，以及 n 应该代表什么。

就算在顶级的 TCS 期刊， TALG 和 TOCS 上，都会简易的指出该算法的时间复杂度是 O(n)，这决定于 n 是怎么定义的。你可以考到大多数 NPC 问题的伪多项式时间算法的 big O 都是这么标注的，如背包， subset sum partition 。当然你说 O(2^n)也是绝对正确，但一切的前提是你必须给出一个严格的定义， O(2^n)这个结论本身就是基于很多严谨的假设基础上才得出的，你不能随便一指就说是 O(2^n)。

@lxiange 令 D 为 N 的二进制表示的位数, 所以你的 n 代表什么

@lxiange 你依然还是不明白什么是 n ，什么是 the length of the string representing the input ，这些都基于你怎么定义的。在没有明确定义 n 的时候， O(2^n) has nothing to do with the given program.