@llhh 当年撸过一个简易的 api ，刚才试了一下竟然还能用。
https://github.com/lxiange/My_FaceRating/blob/master/xiaobingv3.py

这篇博文比较了几种常见的博客类型，适合选择困难症的朋友。
https://lxiange.com/posts/choices-for-personal-blog.html

最后再回复一条，就不一一 @了

其实退一步讲，这并不是一个多么值得探究的问题。
本质上来说，只是消歧义罢了，毕竟大家都知道程序运行起来要多长时间（怪我把函数的参数起名为 n ），
即便这样，是 O(n)还是 O(2^n)，也取决于看待输入的方式。一般定义大 O 表示法的 n 为输入的 length ，
但是大家一般都默认单参数时，把输入的参数的值作为 n ，虽然它和输入的 length 相差了一个指数级。

平时交流、答题时，还算遵守大家的习惯约定就好，具体应该是什么有时反而不重要了。
不然每次讨论几何问题时都要带上 5 条公理，讨论集合问题时都要带上 ZFC 公理，岂不是很累？

和大家撕逼撕得很开心，哈哈~

预祝各位新年快乐！

@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 应该代表什么。

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

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

@qwsqwa
less is more. 感谢回复！

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

@nagato
@xcatliu
前面说过，这种理论问题用编程是不能证明的。不然大家赶紧跑去证明 P!=NP 了，
这个问题的本质歧义就在于 n 的定义上，你可以看一下我前两条回复。看看哪种定义 n 才会引起混乱。
关于 n 的定义，不是自己想怎么认为就怎么认为的，维基百科（ 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 当成“ string representing ”来看么？

@Perry 之前贴了链接了，自己看。可以把引用来源的书拿来看一看。

@sudoz 就是考研的科目编号而已。

@debiann 嘿嘿，我才没有混乱呢，算法的时间复杂度就应该是根据图灵机下的输入规模来评判。

相反，认为是 O(n)，才会引起混乱，

大伙再看看这个函数，时间复杂度是指数级没有歧义吧？
void foo5(char[] arr) {
int num = atoi(arr);
int bar = 0;
for (int i = 0; i < num; i++) {
bar++;
}
}

“ 123456 ”和 123456 ，它们的输入大小几乎是一样的，但凭啥前者是指数复杂度，后者就是线性复杂度了呢？

@xupefei 请看 https://en.wikipedia.org/wiki/Time_complexity 第一句话“... a function of the length of the string representing the input.”

@binux 你的意思是，当输入是数组时，大 O 表示法中的 n 指的是按照数组长度来看待。而输入为一个数时，却指的是其表示的值咯？有点双重标准了吧？同样看一下维基百科第一句话。

@lc4t :)

@jedihy 算法导论上讲的从来都是输入的规模，

@mnzlichunyu 不用看了，算法导论上没有的

@zmj1316 但是图灵机的基本概念总要讲吧？目前的计算理论，都要基于图灵机这个计算模型吧。

@RecursiveG
@xcatliu
@Perry
我做得不好的地方是，写的函数里不应该使用函数这个变量，使得看起来好像“重定义”了 n （其实并没有）
大 O 表示法中的 n ，指的是图灵机下的输入规模（如果把图灵机看成纸带的话，就是输入纸带长度），这点定义得很清楚（不是我定义的，维基百科上也有引用来源供查阅）。而它表示的值，是 10101100 这个数是什么，图灵机是不区分的，只认为它的输入规模为 8 。

输入一个数字，就把它当成大 O 表示法中的 n 。那要是输入一个 double 呢？还是 o （ n ）咯？那再输入一个 char 呢？或者输入一个 string 呢？再输入一个数组？这时候 n 是什么？
不觉得你们才是在不断地“重定义 n ”么？

欢迎打脸，我也希望我是错的，回头我去打 etone :P

@starvedcat 只是想把图灵机的概念用形象的方式来表述罢了。这种纯理论的东西举个栗子会比较形象，但是绝不能用这个例子来当作证明或者通用的方法。。。

@Xs0ul 并没有换定义，大 O 表示法的输入从来就是“长度”，可以去看看维基百科。

@nccers 并没有忽悠，，，从编程上来看，貌似是完全不一样的代码。但是就我想讨论的这个主题，它们没有本质区别啊。




有兴趣的话可以比较这几个函数，按照传统方式理解，有木有觉得有点不对劲？：
https://gist.github.com/lxiange/c82450bf82ee5627f86b2eec834e8d64

@messyidea
@lsmgeb89
@reus
@shakespaces
@AlisaDestiny
@nccers
首先，抱歉评论区的那个代码贴错了（帖子里的代码没错）。
应该是这个（命题人显然自以为答案是根号 n ）：
void foo(int n) {
int sum = 0;
int i = 0;
while (sum < n) {
sum += i++;
}
}

有关算法复杂度，是计算理论的内容，不是“正常人怎么看”的问题。
即使编程的话，也只能去验证而不能去证明。

计算理论这门课水头很深，即使 985 的本科基本都不开这课吧。。？

但是这题还算简单，因为算法时间复杂度的参数 n ，其实指的是图灵机中输入的长度。
举个例子， n=15 ，对应于二进制 1111 ，也就是说，长度是 4 。
循环 16 次，不正好就是 2^n 么？

即时把 n 当成十进制数，从时间复杂度上也是等价于 2^n 的。

当然，没有搞过 TCS 的人是不会注意到这一点的，绝大多数人都不懂的东西，也就只能拿来娱乐娱乐了。

友情提醒，面试时别耍这个小聪明，因为你的面试官肯定也不懂这个 :P

料想到绝大多数人都会认为这个函数时间复杂度是 O(n)，所以特意发帖来引起大家关注。

这里的算法时间复杂度应该是 2^n 。

此题原型为今年考研 408 的一道选择题，原题大意是：
```
void foo1(int n) {
int bar = 0;
for (int i = 0; i < n; i++) {
bar += i++;
}
}
```
我进行了一点点的简化，想突出重点。

虽然不搞 TCS ，但是了解了解算法时间复杂度的计算方法也不是坏处。