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

[lxiange]

不要紧张，请看代码：

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

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

[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]

民科

[v2gba]

这是....冷笑话？

[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]

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