来看看这个函数的时间复杂度是多少 - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
请不要在回答技术问题时复制粘贴 AI 生成的内容
lxiange
V2EX    程序员

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

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

    不要紧张,请看代码:

    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
      &bsp; 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
        69
    slfmessi  
       2016-12-26 10:40:23 +08:00
    所以说选根号 n 是可以得分的吧。。。
    slfmessi
    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     Solana     2712 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 36ms UTC 11:52 PVG 19:52 LAX 04:52 JFK 07:52
    Do have faith in what you're doing.
    ubao snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86