知识卡片

普通读书笔记卡 · 1708.b.2.d · 生成模型:未记录

增长等级刻画规模变化

理解等级:中级

用典型函数观察规模变化,可区分不同增长等级;这里lg是以2为底的对数。

典型函数 随规模变化的含义
1 总成本上界不随规模增长
lg n 每步按固定比例缩小规模所需层数
n 每项做固定量工作
n lg n 约lg n层、每层总计约n工作
n² 两个规模为n的枚举维度
2ⁿ 例如枚举所有子集的数量
n! 例如枚举所有排列的数量

表是典型模型说明,不能看到一次取元素、两个循环或一个递归就自动贴标签;还需核对访问成本、循环边界和每层工作。原书增长表是函数值,不是测得运行时间。

45原始HTML已读取,2ⁿ与3ⁿ的n是上标,不是2n/3n。典型增长次序包含n²lg n、n³、2ⁿ、3ⁿ和n!;T2明确为2ⁿ+n³+25,因此上界O(2ⁿ)。不能用扁平提取文本把指数误改为系数。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      表4-1列出一些常见的复杂计算发生时的复杂度。表4-2列出了当n变化时,这些复杂度的增长速率是如何变化的。图4-1是表4-2的图形式表示。 图 4-1 表4-2的图形化表示 就像一种算法的复杂度几乎不关注算法具体的运行时间,衡量算法的复杂度也没有高效或低效之说。虽然复杂度在一定程度上说明了算法的运算

    • · 查看原书依据

      将算法的复杂度从低到高排列:O(n2)、O(3n)、O(2n)、O(n2 lg n)、O(1)、O(n lg n)、O(n3)、O(n!)、O(lg n)、O(n)? 答:按算法的复杂度从低到高排列为:O(1)、O(lg n)、O(n)、O(n lg n)、O(n2)、O(n2 lg n)、O(n3

    参考来源

    - 位置:《算法精解:C语言描述》第4章《计算的复杂度》(spine1200;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1168.html;u043-ch04-005)。 - 结论依据:43全文和02692-02694两表一曲线实际查看,七种典型增长及样例;表以函数解释而非把大O集合排序为严格相等,未运行基准。 - 原始内容:表4-1列出一些常见的复杂计算发生时的复杂度。表4-2列出了当n变化时,这些复杂度的增长速率是如何变化的。图4-1是表4-2的图形式表示。 图 4-1 表4-2的图形化表示 就像一种算法的复杂度几乎不关注算法具体的运行时间,衡量算法的复杂度也没有高效或低效之说。虽然复杂度在一定程度上说明了算法的运算 - 位置:《算法精解:C语言描述》第4章《问与答》(spine1202;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1170.html;u045-ch04-005)。 - 结论依据:45原始HTML已读取,2ⁿ与3ⁿ的n是上标,不是2n/3n。典型增长次序包含n²lg n、n³、2ⁿ、3ⁿ和n!;T2明确为2ⁿ+n³+25,因此上界O(2ⁿ)。不能用扁平提取文本把指数误改为系数。 - 原始内容:将算法的复杂度从低到高排列:O(n2)、O(3n)、O(2n)、O(n2 lg n)、O(1)、O(n lg n)、O(n3)、O(n!)、O(lg n)、O(n)? 答:按算法的复杂度从低到高排列为:O(1)、O(lg n)、O(n)、O(n lg n)、O(n2)、O(n2 lg n)、O(n3