知识卡片
增长等级刻画规模变化
用典型函数观察规模变化,可区分不同增长等级;这里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