这是一个创建于 2881 天前的主题，其中的信息可能已经有所发展或是发生改变。
不要紧张，请看代码：
void foo1(int n) {
int bar = 0;
for (int i = 0; i < n; i++) {
bar++;
}
}
请问foo1的时间复杂度？:P
 |
1
Kilerd 2016-12-26 00:21:10 +08:00
O(n) 啊
|
 |
2
jedihy 2016-12-26 00:21:29 +08:00
O(n)
|
|
3
Kilerd 2016-12-26 00:21:53 +08:00
问题在于， 为什么不直接 bar = n 呢？ (虽然我知道这是随便写的代码
|
 |
4
lxiange OP 料想到绝大多数人都会认为这个函数时间复杂度是 O(n)，所以特意发帖来引起大家关注。
这里的算法时间复杂度应该是 2^n 。 此题原型为今年考研 408 的一道选择题，原题大意是： ``` void foo1(int n) { int bar = 0; for (int i = 0; i < n; i++) { bar += i++; } } ``` 我进行了一点点的简化，想突出重点。 虽然不搞 TCS ，但是了解了解算法时间复杂度的计算方法也不是坏处。 |
 |
5
messyidea 2016-12-26 00:40:50 +08:00 via Android
没明白为什么是 2^n 。
我感觉还是 O(n) |
 |
6
debiann 2016-12-26 00:42:28 +08:00 via iPhone
就是 O(n)
|
 |
8
reus 2016-12-26 00:59:17 +08:00
不论是 bar++，还是 bar+=i++，时间复杂度都是 O(n)。也就是线性变化的时间复杂度。
|
 |
9
v9ox 2016-12-26 01:02:34 +08:00 via iPhone
O(n)无误
|
 |
10
shakespaces 2016-12-26 01:06:58 +08:00 via Android
恕我愚钝，我想知道 2^n 是怎么来的。。。
|
 |
11
AlisaDestiny 2016-12-26 01:13:08 +08:00
|
 |
12
nccers 2016-12-26 01:14:00 +08:00
我怎么想也想不明白为什么它是 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 开了什么我不知道的优化么? |
|
13
lxiange OP @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 |
 |
14
starvedcat 2016-12-26 01:38:01 +08:00
读了 5 遍终于读明白了。楼主是先求出了输入数据的二进制位数（即以 2 为底的 log ），将该数字指定为 n ，然后说时间复杂度是 2^n 。
就是先求以 2 为底的对数，然后求以 2 为底的幂……………………………… |
|
16
nccers 2016-12-26 01:45:55 +08:00
你真是大忽悠........帖子里的题也是错的好不好,这三个不同的描述根本就是三道题好不好........
|
|
17
debiann 2016-12-26 01:51:35 +08:00 via iPhone
居然把 2 个 n 混着说。。。表达能力有待提高
|
 |
18
xupefei 2016-12-26 01:52:10 +08:00
@lxiange
> 但是这题还算简单，因为算法时间复杂度的参数 n ，其实指的是图灵机中输入的长度。 这完全是你自己的定义。 如果我定义 n 指输入的“大小”，比如题中输入是一个数字，那 n = 1 。这样的话，整体的复杂度是 O(1)。 换一个定义，如果我令 len = 输入数字的大小，那么整体复杂度就是 O(len)，线性。 如果我令 x = 输入数字的二进制长度，那么整体复杂度就是 O(x^2)。 |
|
19
nccers 2016-12-26 01:53:34 +08:00
第三个不是 O(n) 的原因是 sum 的步进不是均匀的,而且 while 循环相当于把 for 循环里的 i 换成 bar 了.....
|
|
20
lxiange OP @starvedcat 只是想把图灵机的概念用形象的方式来表述罢了。这种纯理论的东西举个栗子会比较形象，但是绝不能用这个例子来当作证明或者通用的方法。。。
@Xs0ul 并没有换定义，大 O 表示法的输入从来就是“长度”，可以去看看维基百科。 @nccers 并没有忽悠，，，从编程上来看，貌似是完全不一样的代码。但是就我想讨论的这个主题，它们没有本质区别啊。 有兴趣的话可以比较这几个函数，按照传统方式理解，有木有觉得有点不对劲？： https://gist.github.com/lxiange/c82450bf82ee5627f86b2eec834e8d64 |
 |
21
laxenade 2016-12-26 02:01:09 +08:00
所以楼主想表达什么？
|
|
22
xupefei 2016-12-26 02:09:10 +08:00
|
|
23
nccers 2016-12-26 02:17:30 +08:00  1
你们都不睡觉?...........
|
 |
24
binux 2016-12-26 02:44:45 +08:00
@lxiange 「大 O 表示法的输入从来就」没有规定「是“长度”」，它随什么增长， n 就是什么；或者反过来说，你指定 「 n=15 ，对应于二进制 1111 ，也就是说，长度是 4 （定义为 m ，你不能给同一个符号指定两个含义）」，那么 O(n) = O(2^m)。
大部分时候，复杂度随一元或者二元变化时， n 指的是什么过于显而易见，就直接省略了，但是并不代表它总是长度。 |
 |
25
Ahri 2016-12-26 03:26:43 +08:00 19
民间计算机科学家
|
 |
26
lc4t 2016-12-26 04:30:05 +08:00 via iPhone 2
楼主知道大 O 记号的定义和 n 是怎么来的吗？
|
 |
27
shiji 2016-12-26 04:31:30 +08:00 14
"不要紧张，请看代码："
"料想到绝大多数人都会认为...所以特意发帖...." "虽然不搞 TCS ，但是了解了解算法时间复杂度的计算方法也不是坏处。" "当然，没有搞过 TCS 的人是不会注意到这一点的，绝大多数人都不懂的东西，也就只能拿来娱乐娱乐了。 " "面试时别耍这个小聪明，因为你的面试官肯定也不懂这个" |
|
28
reus 2016-12-26 04:36:07 +08:00 2
原来是连大 O 定义都不懂的民科。
|
 |
29
CosimoZi 2016-12-26 05:07:48 +08:00 3
民科
|
 |
30
MrGba2z 2016-12-26 05:36:54 +08:00 via iPhone
这是....冷笑话？
|
|
31
jedihy 2016-12-26 05:58:22 +08:00
@xupefei 确实是输入长度的限制，这个算法导论上有。这个地方楼主是偷换概念了，我说这个东西时间复杂度是 O(n)是绝对没错的。如果说它的时间复杂度是 o(2^n)，你必须给出 n 的严格定义，不能偷偷把 n 的定义给换了。
|
 |
32
Perry 2016-12-26 05:59:11 +08:00 via iPhone
n 是 digit 还是 bit 不应该在题目里说清楚么？反正随意切换的啊，为什么 digit 的答案就算错了？
|
|
33
jedihy 2016-12-26 06:03:56 +08:00 1
@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)，证毕。 |
 |
34
RecursiveG 2016-12-26 07:26:40 +08:00 2
如果 n 以 binary 表示，则复杂度为 O(2^n)
如果 n 以 unary 表示，则复杂度为 O(n) 既然楼主不说明，那我可以随便挑一种咯? |
 |
35
xcatliu 2016-12-26 08:19:53 +08:00 via iPhone
|
 |
36
zmj1316 2016-12-26 08:23:56 +08:00 via Android
@lxiange hh 敢问 lz 是哪个 985 211 连计算理论都不讲，况且计算理论不是重点在可计算性吗？
|
 |
37
livexia 2016-12-26 08:32:39 +08:00 via Android 2
民科耍小聪明
|
 |
38
owt5008137 2016-12-26 08:49:21 +08:00 via Android
如果开全了编译优化的话，应该是 O(0)吧
|
 |
39
q397064399 2016-12-26 08:51:47 +08:00
@livexia 这不算民科吧，算法复杂度 是中规中矩的 算法与数据结构的入门内容
|
 |
40
Phariel 2016-12-26 08:52:56 +08:00 via Android
吃瓜群众表示：我就喜欢看打脸。
|
 |
41
scnace 2016-12-26 08:54:23 +08:00 via Android
吃瓜群众表示：我就喜欢看打脸。
|
 |
42
WalkingEraser 2016-12-26 08:56:05 +08:00 via Android
学过计算理论的 211 渣本，表示 excuse me ？
|
|
43
Kilerd 2016-12-26 08:57:37 +08:00 via iPhone
第一个回帖的我，现在再来看看。
本以为很菜的我瞬间找到了些许自信。😃😃😃 |
 |
44
mianju 2016-12-26 09:01:13 +08:00
那么问题来了，原题和改卷子算的答案到底是什么？
|
 |
45
mnzlichunyu 2016-12-26 09:11:21 +08:00
吓得我又去看了一下算法导论的第一章。
|
 |
46
mengzhuo 2016-12-26 09:33:56 +08:00 1
excuse me? 这尼玛是 2^n ？回去种地吧
|
 |
47
coderluan 2016-12-26 09:59:43 +08:00
民科笑尿
|
 |
48
zacard 2016-12-26 10:05:14 +08:00
能把原题截图发出来吗。。。不敢相信我滴眼睛。
|
|
49
lxiange OP @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 |
 |
50
xiuc001 2016-12-26 10:09:50 +08:00
O(n)
|
 |
51
kmyzzy 2016-12-26 10:10:11 +08:00 via Android
瞎鸡巴扯
|
|
52
debiann 2016-12-26 10:18:18 +08:00 via iPhone
@lxiange 如果用你采用的这个混乱的符号系统，那么楼上说 O(n)的意思是指 O(n(n)); n(n)=2^n
|
 |
53
nagato 2016-12-26 10:20:20 +08:00
我天，是不是 2^n 你自己去打个 Log 不就知道了吗，辣眼睛啊
|
|
57
Perry 2016-12-26 10:25:58 +08:00 via iPhone
维基百科哪句话说 big O 里的 n 必须是图灵机器的输入？
|
 |
58
ispinfx 2016-12-26 10:26:27 +08:00 via iPhone
很后悔点进来，时间被浪费了。
|
|
59
lxiange OP @debiann 嘿嘿，我才没有混乱呢，算法的时间复杂度就应该是根据图灵机下的输入规模来评判。
相反，认为是 O(n)，才会引起混乱， 大伙再看看这个函数，时间复杂度是指数级没有歧义吧？ void foo5(char[] arr) { int num = atoi(arr); int bar = 0; for (int i = 0; i < num; i++) { bar++; } } “ 123456 ”和 123456 ，它们的输入大小几乎是一样的，但凭啥前者是指数复杂度，后者就是线性复杂度了呢？ |
 |
60
panzhougeek 2016-12-26 10:28:01 +08:00
不知所云。瞎几把扯就楼主最屌了
|
|
61
nagato 2016-12-26 10:30:41 +08:00
@xcatliu 哦这样, n 一般都得自己解释啊，" I think the time complexity of this function is 2^n where n represents the length of the input array..."
|
 |
62
asxalex 2016-12-26 10:31:58 +08:00
唉，浪费我时间
|
|
63
lxiange OP @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 就是考研的科目编号而已。 |
 |
64
raysonx 2016-12-26 10:36:53 +08:00
樓主民科鑑定完畢。
就是 O(n)，沒有疑義。整個算法的執行次數和 n 的大小呈線性關係，再扯其他的都是在扯蛋。 |
|
66
debiann 2016-12-26 10:38:03 +08:00 via iPhone
@lxiange 引起混乱的是你对“输入大小”的错误理解。
比如数字 7 ，你觉得输入就是 111 吗？ 我可以让输入是 1000101010 ，我想怎么输入就怎么输入。只要我对图林机读取的逻辑有完整的定义。 |
 |
67
Shura 2016-12-26 10:39:17 +08:00 via Android
偷换概念
|
 |
68
tim1008 2016-12-26 10:39:57 +08:00
还可以这样装 X...66
|
 |
69
slfmessi 2016-12-26 10:40:23 +08:00
所以说选根号 n 是可以得分的吧。。。
|
 |
70
ipoh 2016-12-26 10:40:39 +08:00 via Android
我来给楼主解释一下，这里 int 我们一般人认为是固定字节长度，所以一次加法操作算是 O(1)
如果 int 是大数，则楼主的说法可以成立，显然楼主可能并不懂我在说什么 |
 |
71
rogerchen 2016-12-26 10:41:06 +08:00 1
楼主是对的，这题跟整数价格 0-1 背包伪多项式时间 O(mn) 一样。多项式时间和伪多项式时间不是一个概念。 RAM 计算模型读入一个 64bit 的数只需要 32bit 的数一倍的时间，但是这个程序需要跑平方那么多的时间，不就是 O(2^n)。平时说的排序 O(nlogn)，读的可是 n 个数。仔细思考一下，不要给人乱扣什么民间计算机科学家的帽子。
|
 |
72
xuefei2062 2016-12-26 10:43:07 +08:00
@lxiange 大 O 表示法的 n 是输入规模啊，大哥，输入规模，输入规模，输入规模
|
 |
73
gimp 2016-12-26 10:43:22 +08:00
重新定义时间复杂度系列？
|
|
74
xcatliu 2016-12-26 10:45:00 +08:00
按你这么说，输入 15 不应该是 1111 ，而是 00000000000000000000000000001111
任何 int 都是 32 位的，输入规模是常数。 |
 |
75
ivvei 2016-12-26 10:46:03 +08:00
连题都不是同一个题……
|
 |
76
jingniao 2016-12-26 10:48:05 +08:00
看楼中间的那位，都有些无语了
|
 |
77
ipwx 2016-12-26 10:48:10 +08:00
一个民间计算机科学家的钓鱼贴你们也回得这么起劲干嘛。
|
|
78
nagato 2016-12-26 10:49:17 +08:00
|
 |
79
muziki 2016-12-26 10:50:08 +08:00 via iPhone
大家散了吧，肯定是题主考研写错题了，出来安慰自己，大 O 这些算法入门课第一讲的东西。
题主不要灰心啦，一选择题而已。说不定大题有更大的惊喜等着你哟。 |
|
80
zmj1316 2016-12-26 11:03:41 +08:00
@lxiange 本科计算理论主要就分两块，可计算性和复杂性，当然都是基于图灵机的。
LZ 用了一个很巧妙的办法把自己绕进去了，就是 用 1111 来 代表了 15 ，推出复杂度是 2^N ，然而从 1111 计算出 15 这个过程就是 2^N 的，如果我直接用 15 个 1 来代表输入，那复杂度还是 N 啊 |
|
81
lxiange OP 1
@rogerchen Cheers ！本来我以为只有 1%的人能做对，结果还不到一百人回复呢，哈哈
@xuefei2062 大哥！我好想把你说的话对你再说一遍啊！ @xcatliu 你说的这个问题这是工程和科学的区别，工程上的局限性导致了所有数都是 32bit 这个固定规模。但是在图灵机模型下就没有这个限制啦~ @nagato 嘿嘿，这个词条也是很严谨的，说的是输入的“ size ”，而不是输入的“ value ”。对于一个 123456 这个数字，你说它的 size 和它的 value 能一样么？ @muziki 因为选项中没有正确答案，连出题人都不懂这个常识。估计绝大多数人也都不懂了吧，所以才拿出来和大家交流交流。 @ipwx 不敢当不敢当，我离科学还远着呢。我只是理解并搬运概念而已，还没厉害到制造概念的地步。 |
 |
82
yanwumo 2016-12-26 11:11:36 +08:00 via Android 1
@lxiange 楼主正确
http://softwareengineering.stackexchange.com/questions/197374/what-is-the-time-complexity-of-the-algorithm-to-check-if-a-number-is-prime 判断一个数是否为质数和楼主的问题是相似的。这类问题的区别在于，问题的规模大小与数字本身的大小有关。 |
|
85
yanwumo 2016-12-26 11:13:48 +08:00 via Android
因此，简单的判断质数的方法不能在多项式时间内完成。
|
|
87
ipwx 2016-12-26 11:16:56 +08:00 7
@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)。 混淆了理论性和工程性的边界，所以说你们是民间科学家。 - - - - 别拿什么考研答案来说事，我还看不上考研这个层次的题目。 |
|
88
lxiange OP @rogerchen 你提到 0-1 背包问题倒是给了我启发。
背包问题是已知的 NPC 问题，并且可以用各位 V 友眼中的“ O(n)时间”求解， 那我们已经证明 P=NP 咯~ 没法再详细解释了，回复了那么多条还不能理解的，也就没必要去理解了，毕竟平时根本用不到这些概念。 各位自以为是的同学们请继续自以为是吧，因为我也会继续“自以为是”的：） 另外，撕逼时应该就事论事。不适合给对方扣帽子，也不要给自己戴高帽，说什么自己来自 985 、上过计算理论、熟读算法导论。也就和小白撕逼时这么做能增强说服力罢了。 @slfmessi 看见老熟人了，惭愧惭愧，今年报了名考研玩玩，还挺有意思的。 “标准答案”是根号 n 。 |
 |
90
iCyMind 2016-12-26 11:23:13 +08:00
运行时间和问题规模成线性关系, 这不就是小学生都懂的 O(n)吗
|
|
91
lxiange OP |
 |
93
mcone 2016-12-26 11:30:36 +08:00
|
 |
94
itqls 2016-12-26 11:34:52 +08:00
高中生都能懂的 n, 在这各种偷换概念. 浪费时间
|
|
95
ivvei 2016-12-26 11:38:56 +08:00
@ipwx 考研题是 while (sum < n) { sum += i++;}， 根本就不是他简化后的 for (int i = 0; i < n; i++) {bar++;}
|
|
97
rogerchen 2016-12-26 11:52:56 +08:00
@ipwx 黑人问号？？？ 算法属于理论计算科学，和电脑，和工程有什么关系？
算法不认识任何实际计算机，只认识图灵机模型， RAM 计算模型。 1 至少用 1 个 bit ， 2^31 至少用 32 个 bit 很难理解么？ 这让我想起当年，因为 int 是 32bit 的，所以所有算法都是常数时间的梗了。 |
|
98
lxiange OP |
Select Language