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

[lxiange]

不要紧张，请看代码：

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

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

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

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