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

[lxiange]

不要紧张，请看代码：

void foo1(int n) {
	int bar = 0;
	for (int i = 0; i < n; i++) {
		bar++;
	}
}

请问foo1的时间复杂度？:P

[lishunan246]

所以答案就是 O(MAX_INT)?

[kmyzzy]

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

[ipoh]

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

[menc]

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

[rogerchen]

http://imgur.com/a/Y29Qw

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

[neoblackcap]

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

[rogerchen]

[rogerchen]

@menc

[rogerchen]

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

[lxiange]

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

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

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

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

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

[ipoh]

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

[ipoh]

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

[lxiange]

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

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

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

[qwsqwa]

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

[jecvay]

int n = 4;
n++;

这复杂度是 O(N) ?

[lxiange]

@qwsqwa
less is more. 感谢回复！

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

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

[jecvay]

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

[neoblackcap]

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

[jsou]

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

[linboki]

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

[muziki]

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

[lxiange]

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

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

[neoblackcap]

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

[ipoh]

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

[jsq2627]

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

[ipoh]

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

[ipoh]

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

[jsq2627]

我试着解释一下
平时我们说的时间复杂度“ 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)

[ipoh]

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

[jhdxr]

@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 这两个不同的定义，给出了两个不同的时间复杂度的结果。

[reus]

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

[jedihy]

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

[jedihy]

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

[jhdxr]

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

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

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

[jsq2627]

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

[v2exhehehehe]

金币赚得好开心

[lxiange]

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

[jedihy]

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

[jecvay]

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

[jedihy]

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

[jedihy]

你如果用你这一套理论，你会对大量算法顶会文章的复杂度计算产生疑惑。

[wshcdr]

时间复杂度为 O （ n ）

[ipoh]

@lxiange 你说的这些概念在算法课上老师都会提到，但是最后老师会说我们一般考虑"加法的时间复杂度是 O(1)"
在这个前提之下才会有这些题目。

[jsq2627]

@reus 还是平常我们对概念理解不够清楚的，平常遇到的大部分是多项式时间的，按那种方式定义 n 恰好结论一致。我希望你能自己看一下我上面贴的那篇 so
http://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time

When working with algorithms that process graphs, lists, trees, etc., this definition more or less agrees with the conventional definition. For example, suppose you have a sorting algorithm that sorts arrays of 32-bit integers. If you use something like selection sort to do this, the runtime, as a function of the number of input elements in the array, will be O(n2). But how does n, the number of elements in the input array, correspond to the the number of bits of input? As mentioned earlier, the number of bits of input will be x = 32n. Therefore, if we express the runtime of the algorithm in terms of x rather than n, we get that the runtime is O(x2), and so the algorithm runs in polynomial time.

[jsq2627]

说到底最终还是歧义的问题，不是思维的问题。

[ipoh]

@jsq2627 他这道题目还是很直白的，普通人都不会认为有歧义

[ipwx]

@laxenade @rogerchen 首先对于“民间科学家”的不当言论表示歉意。但是我仍然有话反驳。

先列出结论：我认为就你们举的这个例子，无论是 O(n) 还是 O(n log2 n) 都是逻辑自洽的，其中 O(n log2 n) 的论述见我之前的回复。当令 k = log2(n)，可得 O(2^k * k)。然而在这里如果我想要把 k 代换成 n 给出 O(2^n * n) 的复杂度就是不恰当的，因为 n 在上下文是有明确含义的，不能把一个符号随意变换含义。

所以对于 O(2^n) 的这个结论，如果按照 n 表示 k 的角度去看，就少了一个 *k 的因子；如果不是这样，那就显然更加离谱了。
- - - -

@rogerchen 对于你说的复杂度分析不应该考虑工程问题，这显然不合适。我们目前的算法都是为了电子计算机设计的，因此所有算法分析和时间复杂度估计都是在电子计算机的前提下成立的；这已经考虑了工程问题。

@laxenade 你说“限制 32bit 的话，那就都变成 O(1)了”，只是大 O 。就算是考虑 32 位整数，在这个例子里面，当限定 n 为 32 位整数， O(15 n) （见我先前的回复）依旧是比 O(15 * 2^32) 更紧的界。同时，算法的复杂度不会小于 Ω(n)。因此 Ω(n) 和 O(15 n) 卡住了这个算法在 32 位整数下的界，因此 Θ(n) 是紧界。

当然如果按照教科书的定义，一切 n < ∞ 的论述都是没有意义的。可是啊，读书不能死扣概念，要领会它的精神。复杂度分析是为了在没有测试算法的前提下估计它的运行时间，当我们有了 32 位整数的大前提下，考虑更细致的界依旧是有意义的，因为我们可以通过计算来估计两个不同算法的优劣。
- - - -

@rogerchen @laxenade 另外还有第二点反驳。你们可能不赞同我说的，“可以定义 i++, sum++, i<n 三个操作为常数时间”。然而你们是出于电子计算机的前提才这么反驳我的。我们谁也不知道将来的量子计算机，乃至什么其他种类的计算机究竟能够有多快，因此我假设这三个操作是 O(1) 是公理，完全不违背理论性。

如果接受这三个假设，那么你们的算法复杂度是 O(n) 是没有错误的结论。当然如果不接受，认为这三个操作的复杂度是 O(log2 n)，那么推出来的结论就是 O(n log2 n)。

当我们考虑 32 位定长整数的电子计算机的时候，也可以认为上述三个操作为 O(1)，得出 O(n) 的结论。

[ivvei]

@jsq2627 为什么我要用 1111 来表示 16 ，而不能用 16 个 1 来表示？ 讨论到特定的输入形式了，那是需要先定义清楚条件的。

[lishunan246]

哪个指令集的整型加减不是 O(1)？好好的一个 C 程序，怎么就扯到计算理论和图灵机上去了？

[lxiange]

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

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

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

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

预祝各位新年快乐！

[binux]

@lxiange 你的错误在于你已经在题目中指定 n 是什么了，还在重用这个符号表示另一个概念，并且不定义 n 是什么。不定义符号摆公式是很民科的行为，就酱。

[xxdd]

O(N)

OVER （滑稽脸）

[21grams]

自作聪明，自以为是，自取其辱

[ic2y]

@rogerchen 哈哈，你是哪个学校的？ ppt 看着眼熟啊

[juleswang]

看不下去了， 楼主一共贴了三段代码：

void foo1(int n) {
int bar = 0;
for (int i = 0; i < n; i++) {
bar++;
}
}

void foo1(int n) {
int bar = 0;
for (int i = 0; i < n; i++) {
bar += i++;
}
}

void foo(int n) {
int sum = 0;
int i = 0;
while (sum < n) {
sum += i++;
}
}

三段代码不完全等同。 我个人认为时间复杂度分别为 O(n), O(sqrt(n)),O(sqrt(n))

[sadscv]

当看到题主说这是考研 408 的题目我当时震惊了。
考研层次的知识被尝试用计算理论去解释它是不合适的。 408 的考察范围也绝不会涉及到这些内容，不然就是命题人的失职 。就像我们看中学数学中介绍的负数不能被开方一样。这些讨论都是有默认的讨论环境的。

[sadscv]

@sadscv 所以我对题主给出的根号 n 的复杂度答案也很疑惑。直到我看某楼贴出来的真正的题目。题主你个标题党，绝对是过度解答了这个问题！！！

[SingeeKing]

我支持 gcc 全优化编译答案是 O(0) XD

[starqoq]

我暗想我和掌柜的等级还很远呢，而且我们掌柜也从不将茴香豆上账。

[hackpro]

默认情况是 O(n)
如果 n 是常数，开了编译器优化后是 O(1)，这玩意在编译阶段就给算出来了

[SoloCompany]

这 sb 问题和下结论说 256-bit AES 加密破解复杂度只有 o(n) 有啥区别
反正你喜欢定义 n=2^256 就好，反正这个数也没多大，一个宇宙也没多大呗

[coymail]

考研 408 不考计算理论，楼主你这纯粹是炫深层知识没有讨论意义啊，只会误导考研的同学

[sonack]

楼主钓鱼？

[kkzxak47]

体育老师任重道远

[ragnaroks]

A 站有个词叫转进如风

[JamesMackerel]

懒得看那么多了。

当时做到那一题，我想了一下时间复杂度肯定小于 n ，其他三个答案都大于 n ，所以我选择根号 n 。也不知道对不对。

[skywayman]

八股文玩死这些书生...

[towser]

以整个函数为基准复杂度当然是 O(n)