首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

请教一个关于算法时间复杂度的问题

  •  
  •   diffworld · 2017-04-08 09:23:52 +08:00 · 1630 次点击
    这是一个创建于 950 天前的主题,其中的信息可能已经有所发展或是发生改变。

    关于算法的时间复杂度,在大话数据结构里面有两个例子

    int sum = 0, n = 100;         /* 执行 1 次 */
    sum = (1 + n) * n / 2;        /* 执行第 1 次 */
    sum = (1 + n) * n / 2;        /* 执行第 2 次 */
    sum = (1 + n) * n / 2;        /* 执行第 3 次 */
    sum = (1 + n) * n / 2;        /* 执行第 4 次 */
    sum = (1 + n) * n / 2;        /* 执行第 5 次 */
    sum = (1 + n) * n / 2;        /* 执行第 6 次 */
    sum = (1 + n) * n / 2;        /* 执行第 7 次 */
    sum = (1 + n) * n / 2;        /* 执行第 8 次 */
    sum = (1 + n) * n / 2;        /* 执行第 9 次 */
    printf("%d", sum);            /* 执行 1 次 */
    

    这段代码的时间复杂度是 O(1)

    而上面的这段代码还可以这样表示

    int n = 10;
    for(int i=0; i<n; i++)
    {
        sum = (1 + 100) * 100 / 2;
    }
    

    这样修改之后代码的时间复杂度是多少? O(1)还是 O(n)?

    12 回复  |  直到 2017-04-08 18:37:22 +08:00
        1
    kindjeff   2017-04-08 09:32:29 +08:00   ♥ 1
    O(1)
        2
    Biwood   2017-04-08 10:01:25 +08:00 via Android   ♥ 1
    下面那段代码的 n 跟上面的不一样吧,如果按照下面的写法, n 为输入值,那么该算法明显是 O(n)
        3
    ipwx   2017-04-08 10:04:52 +08:00   ♥ 2
    复杂度分析是为了在理论上有个客观衡量算法优劣的指标而产生的方法,不是为了抠字眼出考题而产生的方法。

    楼主你不是为了高考在学算法,是为了生产实践。这个东西你说它是 O(n) 和 O(1) 都有道理,我甚至可以认为 O(n log n) 也有道理。

    ( n 在二进制机器上有 log n 长度。为了算 i++,平均复杂度为 log n )。

    与其纠结这些,楼主你还不如纠结一下为什么说快速排序的期望复杂度是 O(n log n),最坏复杂度是 O(n^2)。
        4
    gulucn   2017-04-08 10:24:38 +08:00   ♥ 1
    循环的例子里面 sum 不是循环不变量吗?不知道编译器会不会优化成 O(1)呢?
        5
    xialdj   2017-04-08 10:29:53 +08:00 via iPhone   ♥ 1
    循环次数固定就是 o(1) 不固定就是 o(n)
        6
    diffworld   2017-04-08 11:15:18 +08:00
    @ipwx 你好,你给的建议非常好,我是刚学数据结构的,看大话数据结构只看到第二章觉得这个地方有疑惑就提问了
        7
    Perry   2017-04-08 11:22:37 +08:00 via iPhone
    这样出题目真的很没意思。。不过懂得人一看就是 O(1)
        8
    lecher   2017-04-08 11:44:18 +08:00 via Android
    简单解释就是 O(f(n))指的是算法随数据规模的增长趋势。
    f(n)就是增长函数
    f(n)=1 说明输入数据的数量增加不会影响处理次数。算法的计算次数是常数级别的。
    f(n)=n 说明输入数据的数量增加会导致算法的计算次数成正比增长。表现就是通常一层循环可以完成整个算法的处理,类似 2n 这种单层循环执行两次的, f(n)=2n 会省去常数项,所以也属于 f(n)=n 级别的。
    f(n)=n^2 说明输入数据的数量增加会导致处理次数是成次方指数增长。通常表现就是需要两层循环嵌套处理。

    想了解具体怎么算的,可以看看算法导论第一、第二章,有明确的计算方法。这个涉及高等数学的一些知识点。
        9
    eato   2017-04-08 11:47:06 +08:00 via iPhone
    时间复杂度考虑的是以极限的方式描述算法的运行时间,一般考虑的是最坏的输入情况。像例子中的 n =100 ,可以认为 O(100), 与 O(1) 没有多大区别。
        10
    eato   2017-04-08 13:12:33 +08:00 via iPhone
    @eato fix: n = 10
        11
    ghostheaven   2017-04-08 13:47:45 +08:00 via Android
    修改以后算法时间跟 n 有关,所以是 O(n)。修改之前算法时间跟 n 无关。
        12
    syncher   2017-04-08 18:37:22 +08:00 via Android
    n = 10 的情况下, O(n) = O(10) = O(1)吧
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1005 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 21ms · UTC 19:52 · PVG 03:52 · LAX 11:52 · JFK 14:52
    ♥ Do have faith in what you're doing.