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

[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