V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lxiange
V2EX  ›  程序员

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

  •  
  •   lxiange · 2016-12-26 00:16:20 +08:00 · 12253 次点击
    这是一个创建于 2650 天前的主题,其中的信息可能已经有所发展或是发生改变。

    不要紧张,请看代码:

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

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

    168 条回复    2016-12-27 12:12:41 +08:00
    1  2  
    Kilerd
        1
    Kilerd  
       2016-12-26 00:21:10 +08:00
    O(n) 啊
    jedihy
        2
    jedihy  
       2016-12-26 00:21:29 +08:00
    O(n)
    Kilerd
        3
    Kilerd  
       2016-12-26 00:21:53 +08:00
    问题在于, 为什么不直接 bar = n 呢? (虽然我知道这是随便写的代码
    lxiange
        4
    lxiange  
    OP
       2016-12-26 00:31:12 +08:00
    料想到绝大多数人都会认为这个函数时间复杂度是 O(n),所以特意发帖来引起大家关注。

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

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

    虽然不搞 TCS ,但是了解了解算法时间复杂度的计算方法也不是坏处。
    messyidea
        5
    messyidea  
       2016-12-26 00:40:50 +08:00 via Android
    没明白为什么是 2^n 。
    我感觉还是 O(n)
    debiann
        6
    debiann  
       2016-12-26 00:42:28 +08:00 via iPhone
    就是 O(n)
    lsmgeb89
        7
    lsmgeb89  
       2016-12-26 00:53:19 +08:00
    @lxiange 答案错的吧,这不是正常人看看都是 O(n)
    reus
        8
    reus  
       2016-12-26 00:59:17 +08:00
    不论是 bar++,还是 bar+=i++,时间复杂度都是 O(n)。也就是线性变化的时间复杂度。
    v9ox
        9
    v9ox  
       2016-12-26 01:02:34 +08:00 via iPhone
    O(n)无误
    shakespaces
        10
    shakespaces  
       2016-12-26 01:06:58 +08:00 via Android
    恕我愚钝,我想知道 2^n 是怎么来的。。。
    AlisaDestiny
        11
    AlisaDestiny  
       2016-12-26 01:13:08 +08:00
    @lxiange 当我是小学生么。
    - 这程序不就是求 0+1+2+3+4+。。。。。的前 N 项和和吗?
    - 咋算都是 O(n)。
    nccers
        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 开了什么我不知道的优化么?
    lxiange
        13
    lxiange  
    OP
       2016-12-26 01:28:56 +08:00
    @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
        14
    starvedcat  
       2016-12-26 01:38:01 +08:00
    读了 5 遍终于读明白了。楼主是先求出了输入数据的二进制位数(即以 2 为底的 log ),将该数字指定为 n ,然后说时间复杂度是 2^n 。
    就是先求以 2 为底的对数,然后求以 2 为底的幂………………………………
    Xs0ul
        15
    Xs0ul  
       2016-12-26 01:39:53 +08:00
    @lxiange 所以是给 n 换了个定义?
    nccers
        16
    nccers  
       2016-12-26 01:45:55 +08:00
    你真是大忽悠........帖子里的题也是错的好不好,这三个不同的描述根本就是三道题好不好........
    debiann
        17
    debiann  
       2016-12-26 01:51:35 +08:00 via iPhone
    居然把 2 个 n 混着说。。。表达能力有待提高
    xupefei
        18
    xupefei  
       2016-12-26 01:52:10 +08:00
    @lxiange

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

    如果我定义 n 指输入的“大小”,比如题中输入是一个数字,那 n = 1 。这样的话,整体的复杂度是 O(1)。
    换一个定义,如果我令 len = 输入数字的大小,那么整体复杂度就是 O(len),线性。
    如果我令 x = 输入数字的二进制长度,那么整体复杂度就是 O(x^2)。
    nccers
        19
    nccers  
       2016-12-26 01:53:34 +08:00
    第三个不是 O(n) 的原因是 sum 的步进不是均匀的,而且 while 循环相当于把 for 循环里的 i 换成 bar 了.....
    lxiange
        20
    lxiange  
    OP
       2016-12-26 01:57:39 +08:00
    @starvedcat 只是想把图灵机的概念用形象的方式来表述罢了。这种纯理论的东西举个栗子会比较形象,但是绝不能用这个例子来当作证明或者通用的方法。。。

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

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




    有兴趣的话可以比较这几个函数,按照传统方式理解,有木有觉得有点不对劲?:
    https://gist.github.com/lxiange/c82450bf82ee5627f86b2eec834e8d64
    laxenade
        21
    laxenade  
       2016-12-26 02:01:09 +08:00
    所以楼主想表达什么?
    xupefei
        22
    xupefei  
       2016-12-26 02:09:10 +08:00
    @lxiange 维基并没有说 “长度” 这个定义。具体来说, x 是什么根本没有限制。而且一般说来, “长度” 这个定义一般指的是数组的长度,而不是每个数字的长度。
    nccers
        23
    nccers  
       2016-12-26 02:17:30 +08:00   ❤️ 1
    你们都不睡觉?...........
    binux
        24
    binux  
       2016-12-26 02:44:45 +08:00
    @lxiange 「大 O 表示法的输入从来就」没有规定「是“长度”」,它随什么增长, n 就是什么;或者反过来说,你指定 「 n=15 ,对应于二进制 1111 ,也就是说,长度是 4 (定义为 m ,你不能给同一个符号指定两个含义)」,那么 O(n) = O(2^m)。

    大部分时候,复杂度随一元或者二元变化时, n 指的是什么过于显而易见,就直接省略了,但是并不代表它总是长度。
    Ahri
        25
    Ahri  
       2016-12-26 03:26:43 +08:00   ❤️ 19
    民间计算机科学家
    lc4t
        26
    lc4t  
       2016-12-26 04:30:05 +08:00 via iPhone   ❤️ 2
    楼主知道大 O 记号的定义和 n 是怎么来的吗?
    shiji
        27
    shiji  
       2016-12-26 04:31:30 +08:00   ❤️ 14
    "不要紧张,请看代码:"
    "料想到绝大多数人都会认为...所以特意发帖...."
    "虽然不搞 TCS ,但是了解了解算法时间复杂度的计算方法也不是坏处。"
    "当然,没有搞过 TCS 的人是不会注意到这一点的,绝大多数人都不懂的东西,也就只能拿来娱乐娱乐了。
    "
    "面试时别耍这个小聪明,因为你的面试官肯定也不懂这个"
    reus
        28
    reus  
       2016-12-26 04:36:07 +08:00   ❤️ 2
    原来是连大 O 定义都不懂的民科。
    CosimoZi
        29
    CosimoZi  
       2016-12-26 05:07:48 +08:00   ❤️ 3
    民科
    MrGba2z
        30
    MrGba2z  
       2016-12-26 05:36:54 +08:00 via iPhone
    这是....冷笑话?
    jedihy
        31
    jedihy  
       2016-12-26 05:58:22 +08:00
    @xupefei 确实是输入长度的限制,这个算法导论上有。这个地方楼主是偷换概念了,我说这个东西时间复杂度是 O(n)是绝对没错的。如果说它的时间复杂度是 o(2^n),你必须给出 n 的严格定义,不能偷偷把 n 的定义给换了。
    Perry
        32
    Perry  
       2016-12-26 05:59:11 +08:00 via iPhone
    n 是 digit 还是 bit 不应该在题目里说清楚么?反正随意切换的啊,为什么 digit 的答案就算错了?
    jedihy
        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),证毕。
    RecursiveG
        34
    RecursiveG  
       2016-12-26 07:26:40 +08:00   ❤️ 2
    如果 n 以 binary 表示,则复杂度为 O(2^n)
    如果 n 以 unary 表示,则复杂度为 O(n)
    既然楼主不说明,那我可以随便挑一种咯?
    xcatliu
        35
    xcatliu  
       2016-12-26 08:19:53 +08:00 via iPhone
    @lxiange
    「举个例子, n=15 ,对应于二进制 1111 ,也就是说,长度是 4 。
    循环 16 次,不正好就是 2^n 么?」

    先说 n=15 ,过会又说 n=4 ,这偷换概念太明显了。
    zmj1316
        36
    zmj1316  
       2016-12-26 08:23:56 +08:00 via Android
    @lxiange hh 敢问 lz 是哪个 985 211 连计算理论都不讲,况且计算理论不是重点在可计算性吗?
    livexia
        37
    livexia  
       2016-12-26 08:32:39 +08:00 via Android   ❤️ 2
    民科耍小聪明
    owt5008137
        38
    owt5008137  
       2016-12-26 08:49:21 +08:00 via Android
    如果开全了编译优化的话,应该是 O(0)吧
    q397064399
        39
    q397064399  
       2016-12-26 08:51:47 +08:00
    @livexia 这不算民科吧,算法复杂度 是中规中矩的 算法与数据结构的入门内容
    Phariel
        40
    Phariel  
       2016-12-26 08:52:56 +08:00 via Android
    吃瓜群众表示:我就喜欢看打脸。
    scnace
        41
    scnace  
       2016-12-26 08:54:23 +08:00 via Android
    吃瓜群众表示:我就喜欢看打脸。
    WalkingEraser
        42
    WalkingEraser  
       2016-12-26 08:56:05 +08:00 via Android
    学过计算理论的 211 渣本,表示 excuse me ?
    Kilerd
        43
    Kilerd  
       2016-12-26 08:57:37 +08:00 via iPhone
    第一个回帖的我,现在再来看看。
    本以为很菜的我瞬间找到了些许自信。😃😃😃
    mianju
        44
    mianju  
       2016-12-26 09:01:13 +08:00
    那么问题来了,原题和改卷子算的答案到底是什么?
    mnzlichunyu
        45
    mnzlichunyu  
       2016-12-26 09:11:21 +08:00
    吓得我又去看了一下算法导论的第一章。
    mengzhuo
        46
    mengzhuo  
       2016-12-26 09:33:56 +08:00   ❤️ 1
    excuse me? 这尼玛是 2^n ?回去种地吧
    coderluan
        47
    coderluan  
       2016-12-26 09:59:43 +08:00
    民科笑尿
    zacard
        48
    zacard  
       2016-12-26 10:05:14 +08:00
    能把原题截图发出来吗。。。不敢相信我滴眼睛。
    lxiange
        49
    lxiange  
    OP
       2016-12-26 10:05:25 +08:00
    @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
        50
    xiuc001  
       2016-12-26 10:09:50 +08:00
    O(n)
    kmyzzy
        51
    kmyzzy  
       2016-12-26 10:10:11 +08:00 via Android
    瞎鸡巴扯
    debiann
        52
    debiann  
       2016-12-26 10:18:18 +08:00 via iPhone
    @lxiange 如果用你采用的这个混乱的符号系统,那么楼上说 O(n)的意思是指 O(n(n)); n(n)=2^n
    nagato
        53
    nagato  
       2016-12-26 10:20:20 +08:00
    我天,是不是 2^n 你自己去打个 Log 不就知道了吗,辣眼睛啊
    Inn0cence
        54
    Inn0cence  
       2016-12-26 10:21:56 +08:00
    @nccers CPU 分支预测
    xcatliu
        55
    xcatliu  
       2016-12-26 10:24:42 +08:00
    @nagato 让他自己去打个 log 他还是会认为他是对的,因为他的 n 和你定义的 n 不同。。
    sudoz
        56
    sudoz  
       2016-12-26 10:24:59 +08:00
    @lxiange 考研 408 是什么?
    Perry
        57
    Perry  
       2016-12-26 10:25:58 +08:00 via iPhone
    维基百科哪句话说 big O 里的 n 必须是图灵机器的输入?
    ispinfx
        58
    ispinfx  
       2016-12-26 10:26:27 +08:00 via iPhone
    很后悔点进来,时间被浪费了。
    lxiange
        59
    lxiange  
    OP
       2016-12-26 10:27:30 +08:00
    @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
        60
    panzhougeek  
       2016-12-26 10:28:01 +08:00
    不知所云。瞎几把扯就楼主最屌了
    nagato
        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..."
    asxalex
        62
    asxalex  
       2016-12-26 10:31:58 +08:00
    唉,浪费我时间
    lxiange
        63
    lxiange  
    OP
       2016-12-26 10:36:41 +08:00
    @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
        64
    raysonx  
       2016-12-26 10:36:53 +08:00
    樓主民科鑑定完畢。
    就是 O(n),沒有疑義。整個算法的執行次數和 n 的大小呈線性關係,再扯其他的都是在扯蛋。
    ipoh
        65
    ipoh  
       2016-12-26 10:37:13 +08:00 via Android
    @lxiange 你这个 foo5 什么叫 "输入大小几乎一样"
    debiann
        66
    debiann  
       2016-12-26 10:38:03 +08:00 via iPhone
    @lxiange 引起混乱的是你对“输入大小”的错误理解。
    比如数字 7 ,你觉得输入就是 111 吗?
    我可以让输入是 1000101010 ,我想怎么输入就怎么输入。只要我对图林机读取的逻辑有完整的定义。
    Shura
        67
    Shura  
       2016-12-26 10:39:17 +08:00 via Android
    偷换概念
    tim1008
        68
    tim1008  
       2016-12-26 10:39:57 +08:00
    还可以这样装 X...66
    slfmessi
        69
    slfmessi  
       2016-12-26 10:40:23 +08:00
    所以说选根号 n 是可以得分的吧。。。
    ipoh
        70
    ipoh  
       2016-12-26 10:40:39 +08:00 via Android
    我来给楼主解释一下,这里 int 我们一般人认为是固定字节长度,所以一次加法操作算是 O(1)
    如果 int 是大数,则楼主的说法可以成立,显然楼主可能并不懂我在说什么
    rogerchen
        71
    rogerchen  
       2016-12-26 10:41:06 +08:00   ❤️ 1
    楼主是对的,这题跟整数价格 0-1 背包伪多项式时间 O(mn) 一样。多项式时间和伪多项式时间不是一个概念。 RAM 计算模型读入一个 64bit 的数只需要 32bit 的数一倍的时间,但是这个程序需要跑平方那么多的时间,不就是 O(2^n)。平时说的排序 O(nlogn),读的可是 n 个数。仔细思考一下,不要给人乱扣什么民间计算机科学家的帽子。
    xuefei2062
        72
    xuefei2062  
       2016-12-26 10:43:07 +08:00
    @lxiange 大 O 表示法的 n 是输入规模啊,大哥,输入规模,输入规模,输入规模
    gimp
        73
    gimp  
       2016-12-26 10:43:22 +08:00
    重新定义时间复杂度系列?
    xcatliu
        74
    xcatliu  
       2016-12-26 10:45:00 +08:00
    按你这么说,输入 15 不应该是 1111 ,而是 00000000000000000000000000001111
    任何 int 都是 32 位的,输入规模是常数。
    ivvei
        75
    ivvei  
       2016-12-26 10:46:03 +08:00
    连题都不是同一个题……
    jingniao
        76
    jingniao  
       2016-12-26 10:48:05 +08:00
    看楼中间的那位,都有些无语了
    ipwx
        77
    ipwx  
       2016-12-26 10:48:10 +08:00
    一个民间计算机科学家的钓鱼贴你们也回得这么起劲干嘛。
    nagato
        78
    nagato  
       2016-12-26 10:49:17 +08:00
    @lxiange 你英语有问题
    另外你搞错了,我想你应该参考的是 Big O 的解释
    https://en.wikipedia.org/wiki/Big_O_notation
    muziki
        79
    muziki  
       2016-12-26 10:50:08 +08:00 via iPhone
    大家散了吧,肯定是题主考研写错题了,出来安慰自己,大 O 这些算法入门课第一讲的东西。

    题主不要灰心啦,一选择题而已。说不定大题有更大的惊喜等着你哟。
    zmj1316
        80
    zmj1316  
       2016-12-26 11:03:41 +08:00
    @lxiange 本科计算理论主要就分两块,可计算性和复杂性,当然都是基于图灵机的。

    LZ 用了一个很巧妙的办法把自己绕进去了,就是 用 1111 来 代表了 15 ,推出复杂度是 2^N ,然而从 1111 计算出 15 这个过程就是 2^N 的,如果我直接用 15 个 1 来代表输入,那复杂度还是 N 啊
    lxiange
        81
    lxiange  
    OP
       2016-12-26 11:05:17 +08:00   ❤️ 1
    @rogerchen Cheers !本来我以为只有 1%的人能做对,结果还不到一百人回复呢,哈哈

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

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

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

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

    @ipwx 不敢当不敢当,我离科学还远着呢。我只是理解并搬运概念而已,还没厉害到制造概念的地步。
    yanwumo
        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
    判断一个数是否为质数和楼主的问题是相似的。这类问题的区别在于,问题的规模大小与数字本身的大小有关。
    ipoh
        83
    ipoh  
       2016-12-26 11:12:13 +08:00
    @zmj1316 但是他的失误是写的代码而不是用语言描述的
    ipoh
        84
    ipoh  
       2016-12-26 11:12:48 +08:00
    @yanwumo 但是他写的是代码,你们别被他绕进去了
    yanwumo
        85
    yanwumo  
       2016-12-26 11:13:48 +08:00 via Android
    因此,简单的判断质数的方法不能在多项式时间内完成。
    yanwumo
        86
    yanwumo  
       2016-12-26 11:14:48 +08:00 via Android
    @ipoh 是的,楼主的失误就在于他写成了代码,问题就变成用 int 实现时间复杂度是怎样了。
    ipwx
        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)。

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

    别拿什么考研答案来说事,我还看不上考研这个层次的题目。
    lxiange
        88
    lxiange  
    OP
       2016-12-26 11:19:52 +08:00
    @rogerchen 你提到 0-1 背包问题倒是给了我启发。

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

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

    各位自以为是的同学们请继续自以为是吧,因为我也会继续“自以为是”的:)

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

    @slfmessi 看见老熟人了,惭愧惭愧,今年报了名考研玩玩,还挺有意思的。
    “标准答案”是根号 n 。
    zmj1316
        89
    zmj1316  
       2016-12-26 11:23:06 +08:00 via Android
    @lxiange 然而我还是不清楚你对一开始的代码所定义的复杂度是多少
    iCyMind
        90
    iCyMind  
       2016-12-26 11:23:13 +08:00
    运行时间和问题规模成线性关系, 这不就是小学生都懂的 O(n)吗
    lxiange
        91
    lxiange  
    OP
       2016-12-26 11:23:50 +08:00
    @ipoh
    @yanwumo
    嗯嗯,我确实错了。
    严格说,单就这个代码而言,最坏时间复杂度应该是 o(1),常数级,这个常数为 2^32 ,哈哈
    ipoh
        92
    ipoh  
       2016-12-26 11:26:09 +08:00
    @lxiange 好好看看人家 @ipwx 的解释,另外承认错误并不是什么丢脸的事,这么多人给你指出问题你还视而不见。。
    mcone
        93
    mcone  
       2016-12-26 11:30:36 +08:00
    @ipwx 我刚想码字刷新了下看到你的回复 我就不想码字了 给你个赞吧
    这个讨论我认真看了下来,要不是花时间冷静下理了理,我还真觉得我三观被颠覆了——好吧,我承认本科时候没有认真学习,三观这么容易就被忽悠了

    另外多说句看到这个回复
    > @rogerchen Cheers !本来我以为只有 1%的人能做对,结果还不到一百人回复呢,哈哈
    你的回复已经在 81 楼了,题主你的概率论真的也得好好学学了,真心的,不然别人说你是民间科学家一点都不亏
    itqls
        94
    itqls  
       2016-12-26 11:34:52 +08:00
    高中生都能懂的 n, 在这各种偷换概念. 浪费时间
    ivvei
        95
    ivvei  
       2016-12-26 11:38:56 +08:00
    @ipwx 考研题是 while (sum < n) { sum += i++;}, 根本就不是他简化后的 for (int i = 0; i < n; i++) {bar++;}
    ipoh
        96
    ipoh  
       2016-12-26 11:49:58 +08:00
    @ivvei 难怪他说标准答案是根号 n
    rogerchen
        97
    rogerchen  
       2016-12-26 11:52:56 +08:00
    @ipwx 黑人问号??? 算法属于理论计算科学,和电脑,和工程有什么关系?
    算法不认识任何实际计算机,只认识图灵机模型, RAM 计算模型。 1 至少用 1 个 bit , 2^31 至少用 32 个 bit 很难理解么?

    这让我想起当年,因为 int 是 32bit 的,所以所有算法都是常数时间的梗了。
    lxiange
        98
    lxiange  
    OP
       2016-12-26 11:58:28 +08:00
    @ipwx 我很清楚你在说什么,但是我很难在很短的篇幅内反驳你,所以暂且不表(看起来你部分同意我的观点,其实分歧更大)。

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

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

    就事论事,别乱给人扣帽子,一定要在某给方面钻牛角尖打压对方以求精神胜利法的话,,,,,,那我也就认了。。。囧 rz
    ipoh
        99
    ipoh  
       2016-12-26 12:01:21 +08:00 via Android
    @rogerchen int 是 32bit 是怎么推出算法都是常数时间的
    rogerchen
        100
    rogerchen  
       2016-12-26 12:09:09 +08:00   ❤️ 1
    @ipoh 输入规模被框定了,比如 G(V, E),最多有 2^31-1 个节点,最多有 2^31-1 条边。任何给定宽度的原始数据类型都面临这个问题,能够表达的数据规模是有限的。有限的就是常数时间。如果非要说 int 是 32 位的,楼主的算法时间复杂度是无穷大,因为输入的规模 32bit 没有变,运行时间发生了变化。

    这种事情没什么好争的, 能插得上嘴的都知道双方纠结的点在哪。我只是觉得很多人嘲讽楼主不对,指数和线性的观点都有合理性。
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2669 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 15:27 · PVG 23:27 · LAX 08:27 · JFK 11:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.