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

[lxiange]

不要紧张，请看代码：

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

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

[Kilerd]

O(n) 啊

[jedihy]

O(n)

[Kilerd]

问题在于， 为什么不直接 bar = n 呢？ (虽然我知道这是随便写的代码

[lxiange]

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

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

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

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

[messyidea]

没明白为什么是 2^n 。
我感觉还是 O(n)

[debiann]

就是 O(n)

[lsmgeb89]

@lxiange 答案错的吧，这不是正常人看看都是 O(n)

[reus]

不论是 bar++，还是 bar+=i++，时间复杂度都是 O(n)。也就是线性变化的时间复杂度。

[v9ox]

O(n)无误

[shakespaces]

恕我愚钝，我想知道 2^n 是怎么来的。。。

[AlisaDestiny]

@lxiange 当我是小学生么。
- 这程序不就是求 0+1+2+3+4+。。。。。的前 N 项和和吗？
- 咋算都是 O(n)。

[nccers]

我怎么想也想不明白为什么它是 O(2^n) 的,于是稍微试了一下,写的东西是这样的.
#include<stdio.h>
#include<stdlib.h>

long long convert(int);
int main(int argc, char *argv[]) {
const char *str = argv[1];
printf("str = %s\n", str);
int n = atoi(str);
long long bar = convert(n);
printf("bar = %lld\n", bar);
return 0;
}
long long convert(int n) {
long long bar = 0;
for(int i = 0;i < n;i++) {
bar += (long long)i++;
}
return bar;
}
然后结果是这样的
n = 1x10^7
time ./a.out 10000000
str = 10000000
bar = 24999995000000

real 0m0.030s
user 0m0.026s
sys 0m0.002s

n = 1x10^8
time ./a.out 100000000
str = 100000000
bar = 2499999950000000

real 0m0.241s
user 0m0.235s
sys 0m0.002s

n = 1x10^9
time ./a.out 1000000000
str = 1000000000
bar = 249999999500000000

real 0m2.345s
user 0m2.337s
sys 0m0.004s
再大就溢出了......
请问是 gcc 开了什么我不知道的优化么?

[lxiange]

@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

[starvedcat]

读了 5 遍终于读明白了。楼主是先求出了输入数据的二进制位数（即以 2 为底的 log ），将该数字指定为 n ，然后说时间复杂度是 2^n 。
就是先求以 2 为底的对数，然后求以 2 为底的幂………………………………

[Xs0ul]

@lxiange 所以是给 n 换了个定义？

[nccers]

你真是大忽悠........帖子里的题也是错的好不好,这三个不同的描述根本就是三道题好不好........

[debiann]

居然把 2 个 n 混着说。。。表达能力有待提高

[xupefei]

@lxiange

> 但是这题还算简单，因为算法时间复杂度的参数 n ，其实指的是图灵机中输入的长度。
这完全是你自己的定义。

如果我定义 n 指输入的“大小”，比如题中输入是一个数字，那 n = 1 。这样的话，整体的复杂度是 O(1)。
换一个定义，如果我令 len = 输入数字的大小，那么整体复杂度就是 O(len)，线性。
如果我令 x = 输入数字的二进制长度，那么整体复杂度就是 O(x^2)。

[nccers]

第三个不是 O(n) 的原因是 sum 的步进不是均匀的,而且 while 循环相当于把 for 循环里的 i 换成 bar 了.....

[lxiange]

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

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

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




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

[laxenade]

所以楼主想表达什么？

[xupefei]

@lxiange 维基并没有说 “长度” 这个定义。具体来说， x 是什么根本没有限制。而且一般说来， “长度” 这个定义一般指的是数组的长度，而不是每个数字的长度。

[nccers]

你们都不睡觉?...........

[binux]

@lxiange 「大 O 表示法的输入从来就」没有规定「是“长度”」，它随什么增长， n 就是什么；或者反过来说，你指定 「 n=15 ，对应于二进制 1111 ，也就是说，长度是 4 （定义为 m ，你不能给同一个符号指定两个含义）」，那么 O(n) = O(2^m)。

大部分时候，复杂度随一元或者二元变化时， n 指的是什么过于显而易见，就直接省略了，但是并不代表它总是长度。

[Ahri]

民间计算机科学家

[lc4t]

楼主知道大 O 记号的定义和 n 是怎么来的吗？

[shiji]

"不要紧张，请看代码："
"料想到绝大多数人都会认为...所以特意发帖...."
"虽然不搞 TCS ，但是了解了解算法时间复杂度的计算方法也不是坏处。"
"当然，没有搞过 TCS 的人是不会注意到这一点的，绝大多数人都不懂的东西，也就只能拿来娱乐娱乐了。
"
"面试时别耍这个小聪明，因为你的面试官肯定也不懂这个"

[reus]

原来是连大 O 定义都不懂的民科。

[CosimoZi]

民科

[MrGba2z]

这是....冷笑话？

[jedihy]

@xupefei 确实是输入长度的限制，这个算法导论上有。这个地方楼主是偷换概念了，我说这个东西时间复杂度是 O(n)是绝对没错的。如果说它的时间复杂度是 o(2^n)，你必须给出 n 的严格定义，不能偷偷把 n 的定义给换了。

[Perry]

n 是 digit 还是 bit 不应该在题目里说清楚么？反正随意切换的啊，为什么 digit 的答案就算错了？

[jedihy]

@lxiange 不过是从算法理论角度还是其他角度，你都错了，你重定义了 n 。
他的时间复杂度是可以等于 O(2^m)，但是 m = log_2 n = maximum number of bits in variable n 。
O(2^m) = O(2^(log_2 n)) = O(n)，证毕。

[RecursiveG]

如果 n 以 binary 表示，则复杂度为 O(2^n)
如果 n 以 unary 表示，则复杂度为 O(n)
既然楼主不说明，那我可以随便挑一种咯?

[xcatliu]

@lxiange
「举个例子， n=15 ，对应于二进制 1111 ，也就是说，长度是 4 。
循环 16 次，不正好就是 2^n 么？」

先说 n=15 ，过会又说 n=4 ，这偷换概念太明显了。

[zmj1316]

@lxiange hh 敢问 lz 是哪个 985 211 连计算理论都不讲，况且计算理论不是重点在可计算性吗？

[livexia]

民科耍小聪明

[owt5008137]

如果开全了编译优化的话，应该是 O(0)吧

[q397064399]

@livexia 这不算民科吧，算法复杂度 是中规中矩的 算法与数据结构的入门内容

[Phariel]

吃瓜群众表示：我就喜欢看打脸。

[scnace]

吃瓜群众表示：我就喜欢看打脸。

[WalkingEraser]

学过计算理论的 211 渣本，表示 excuse me ？

[Kilerd]

第一个回帖的我，现在再来看看。
本以为很菜的我瞬间找到了些许自信。😃😃😃

[mianju]

那么问题来了，原题和改卷子算的答案到底是什么？

[mnzlichunyu]

吓得我又去看了一下算法导论的第一章。

[mengzhuo]

excuse me? 这尼玛是 2^n ？回去种地吧

[coderluan]

民科笑尿

[zacard]

能把原题截图发出来吗。。。不敢相信我滴眼睛。

[lxiange]

@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

[xiuc001]

O(n)

[kmyzzy]

瞎鸡巴扯

[debiann]

@lxiange 如果用你采用的这个混乱的符号系统，那么楼上说 O(n)的意思是指 O(n(n)); n(n)=2^n

[nagato]

我天，是不是 2^n 你自己去打个 Log 不就知道了吗，辣眼睛啊

[Inn0cence]

@nccers CPU 分支预测

[xcatliu]

@nagato 让他自己去打个 log 他还是会认为他是对的，因为他的 n 和你定义的 n 不同。。

[sudoz]

@lxiange 考研 408 是什么？

[Perry]

维基百科哪句话说 big O 里的 n 必须是图灵机器的输入？

[ispinfx]

很后悔点进来，时间被浪费了。

[lxiange]

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

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

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

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

[panzhougeek]

不知所云。瞎几把扯就楼主最屌了

[nagato]

@xcatliu 哦这样, n 一般都得自己解释啊，" I think the time complexity of this function is 2^n where n represents the length of the input array..."

[asxalex]

唉，浪费我时间

[lxiange]

@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 就是考研的科目编号而已。

[raysonx]

樓主民科鑑定完畢。
就是 O(n)，沒有疑義。整個算法的執行次數和 n 的大小呈線性關係，再扯其他的都是在扯蛋。

[ipoh]

@lxiange 你这个 foo5 什么叫 "输入大小几乎一样"

[debiann]

@lxiange 引起混乱的是你对“输入大小”的错误理解。
比如数字 7 ，你觉得输入就是 111 吗？
我可以让输入是 1000101010 ，我想怎么输入就怎么输入。只要我对图林机读取的逻辑有完整的定义。

[Shura]

偷换概念

[tim1008]

还可以这样装 X...66

[slfmessi]

所以说选根号 n 是可以得分的吧。。。

[ipoh]

我来给楼主解释一下，这里 int 我们一般人认为是固定字节长度，所以一次加法操作算是 O(1)
如果 int 是大数，则楼主的说法可以成立，显然楼主可能并不懂我在说什么

[rogerchen]

楼主是对的，这题跟整数价格 0-1 背包伪多项式时间 O(mn) 一样。多项式时间和伪多项式时间不是一个概念。 RAM 计算模型读入一个 64bit 的数只需要 32bit 的数一倍的时间，但是这个程序需要跑平方那么多的时间，不就是 O(2^n)。平时说的排序 O(nlogn)，读的可是 n 个数。仔细思考一下，不要给人乱扣什么民间计算机科学家的帽子。

[xuefei2062]

@lxiange 大 O 表示法的 n 是输入规模啊，大哥，输入规模，输入规模，输入规模

[gimp]

重新定义时间复杂度系列？

[xcatliu]

按你这么说，输入 15 不应该是 1111 ，而是 00000000000000000000000000001111
任何 int 都是 32 位的，输入规模是常数。

[ivvei]

连题都不是同一个题……

[jingniao]

看楼中间的那位，都有些无语了

[ipwx]

一个民间计算机科学家的钓鱼贴你们也回得这么起劲干嘛。

[nagato]

@lxiange 你英语有问题
另外你搞错了，我想你应该参考的是 Big O 的解释
https://en.wikipedia.org/wiki/Big_O_notation

[muziki]

大家散了吧，肯定是题主考研写错题了，出来安慰自己，大 O 这些算法入门课第一讲的东西。

题主不要灰心啦，一选择题而已。说不定大题有更大的惊喜等着你哟。

[zmj1316]

@lxiange 本科计算理论主要就分两块，可计算性和复杂性，当然都是基于图灵机的。

LZ 用了一个很巧妙的办法把自己绕进去了，就是 用 1111 来 代表了 15 ，推出复杂度是 2^N ，然而从 1111 计算出 15 这个过程就是 2^N 的，如果我直接用 15 个 1 来代表输入，那复杂度还是 N 啊

[lxiange]

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

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

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

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

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

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

[yanwumo]

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

[ipoh]

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

[ipoh]

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

[yanwumo]

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

[yanwumo]

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

[ipwx]

@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)。

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

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

[lxiange]

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

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

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

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

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

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

[zmj1316]

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

[iCyMind]

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

[lxiange]

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

[ipoh]

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

[mcone]

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

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

[itqls]

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

[ivvei]

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

[ipoh]

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

[rogerchen]

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

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

[lxiange]

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

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

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

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

[ipoh]

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

[rogerchen]

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

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