知识卡片
成本组合按实际次数求和
按非负成本模型,顺序执行的成本先相加,重复执行要按实际次数累加。独立的n次外循环每次都做n次内工作,可得n²量级;内层次数依赖外层时,则不能机械把两个最大次数相乘当精确计数。
固定正系数与低阶项在描述渐近等级时可吸收进常数,例如3n²+10n+10属于O(n²)。丢弃系数是换一种精度描述,不是说该系数实际耗时占比会消失。
原式小算例校正:n=10总量410,高阶项300占约73.17%,常数10占约2.44%;n=100总量31010,高阶项30000占约96.74%。这些是公式演算,原文常数百分比/指数排印有误,不是运行测量。
45按逐个相加的方案执行m−1次方阵加法,每次O(n²),得O(mn²)上界;k+n在非负k≤n约束下是O(n),失去约束就应保留k。这里是特定操作方案/模型,不是证明所有矩阵任务都有同一成本。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 成本组合按实际次数求和
- · 问与答
原书出处 · 2 处
- · 查看原书依据
加法运算取最大值。当分析一个算法的运行时间时,如果一个任务在另一个任务之后顺序执行,可以运用此规则。例如,有两个顺序执行的任务,其运行时间分别为:T1(n)=n和T2(n)=n2,运行结果表示为O(n)+O(n2),根据规则,可以简化为O(n2)。正式地表述为: O(T1)+O(T2)=O(T1+T
- · 查看原书依据
添加m个大小为n×n的方阵,如果添加两个这样的方阵所消耗的运行时间为O(n2),那么请用m和n表示此过程的复杂度。 答:要添加m个n×n方阵,必须做m-1次加法运算,每次运算消耗的运行时间为O(n2),所以此过程的总体运行时间为:O(m-1)O(n2)=O(m)O(n2)=O(mn2)。 问:假设有
参考来源
- 位置:《算法精解:C语言描述》第4章《O表示法》(spine1199;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1167.html;u042-ch04-004)。
- 结论依据:42原始HTML全读,确认sup/sub、四条规则及3n²+10n+10算式;百分数按所给公式直接算得,明确为读者演算纠错而非原文统计。
- 原始内容:加法运算取最大值。当分析一个算法的运行时间时,如果一个任务在另一个任务之后顺序执行,可以运用此规则。例如,有两个顺序执行的任务,其运行时间分别为:T1(n)=n和T2(n)=n2,运行结果表示为O(n)+O(n2),根据规则,可以简化为O(n2)。正式地表述为: O(T1)+O(T2)=O(T1+T
- 位置:《算法精解:C语言描述》第4章《问与答》(spine1202;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1170.html;u045-ch04-004)。
- 结论依据:45按逐个相加的方案执行m−1次方阵加法,每次O(n²),得O(mn²)上界;k+n在非负k≤n约束下是O(n),失去约束就应保留k。这里是特定操作方案/模型,不是证明所有矩阵任务都有同一成本。
- 原始内容:添加m个大小为n×n的方阵,如果添加两个这样的方阵所消耗的运行时间为O(n2),那么请用m和n表示此过程的复杂度。 答:要添加m个n×n方阵,必须做m-1次加法运算,每次运算消耗的运行时间为O(n2),所以此过程的总体运行时间为:O(m-1)O(n2)=O(m)O(n2)=O(mn2)。 问:假设有