算法设计与分析第二章学习指南

视频

https://www.icourse163.org/course/HIT-356006

算法设计与分析(基础篇) 第二讲 2.1-2.3

阅读

算法导论(第三版) 第三章，4.3-4.5 节，4.6 节(选读)

练习题

(1) 证明或否证：f (n)+o(f(n))=Θ(f(n))

(2) 证明：Θ(f(x)) + O(g(x)) = O( max(f(x), g(x))).

(3) 证明或给出反例：Θ(f(n))∩o(f(n))=∅

(4) 证明：设 k 是任意常数正整数，则 log

k

n = o(n)

(5) 证明：logn!=Θ(nlogn)

(6) 用迭代法解方程 T(n)＝T(9n/10)+n

(7) 解方程 T(n)=6T(n/3)+logn

(8) 解方程 T(n) =3T(n/3 +5) + n/2

(9) 解方程 T(n)= T (n/2 )+1

(10) 解方程 T(n)=9T(n/3)+n

(11) 解方程 T(n)=T( ⎣n/2⎦ )+n

3

(12) 证明或否证：如果 f(n)=O(g(n))，那么 2

f(n)

=O(2

g(n)

)

(13) 令 f, g 和 h 为定义在正整数上的正实数函数。假设 f(n)=O(g(n))，g(n)=O(h(n))，

证明 f(n)=O(h(n)).

(14) 将下列函数按它们在 n→∞时的无穷大阶数，从小到大排序。

n, n

lg

7

, n

2.5

, n

3

lgn, n

2

lgn, nlgn

(15) 一个时间复杂性为 O(n

2

)的算法的运行时间一定大于一个时间复杂性为 O(n)

的算法么？为什么？

思考题

维基百科中的 Master 定理描述和算法导论不同，思考其差别以及哪个正确？(维

基百科中的 Master 定理描述如下)

算法设计与分析第二章1

analysis:算法设计与分析基础

算法分析与设计：半数集问题

算法设计与分析-王秋芬(改）.rar

算法设计与分析第四章1

算法设计与分析（王晓东） 算法设计与分析电子教案

算法设计与分析（第二版）王红梅，胡明 第一章课后答案

算法设计与分析：第3章 分治法.pdf

算法设计与分析（第二版）程序源码

算法设计与分析：第2章 递归法.pdf

算法设计与分析课件-第二章 算法效率分析基础.ppt

算法设计与分析答案.pdf

（陈慧南 第3版）算法设计与分析——课后习题答案（1~8章）

算法设计与分析（第2版）参考答案.rar

算法设计与分析：第5章 动态规划法.pdf

算法设计与分析 王红梅

算法设计与分析课后习题答案（c++）

李春葆.zip 李春葆 算法设计与分析2nd习题答案代码课件

算法设计与分析基础（第二版）课后习题解答答案

算法设计与分析（第2版）课后习题答案

算法设计与分析：第2章 算法分析基础.ppt

算法设计与分析课后习题答案（李春保）

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

安全认证cisp教材全套

OpenVAS GVM 中文翻译补丁

2024最新：Hvv中常见的面试问题

最新资源

算法设计与分析（王晓东）算法设计与分析电子教案

算法设计与分析（第二版）王红梅，胡明第一章课后答案

算法设计与分析：第3章分治法.pdf

算法设计与分析：第2章递归法.pdf

算法设计与分析课件-第二章算法效率分析基础.ppt

（陈慧南第3版）算法设计与分析——课后习题答案（1~8章）

算法设计与分析：第5章动态规划法.pdf

算法设计与分析王红梅

李春葆.zip 李春葆算法设计与分析2nd习题答案代码课件

算法设计与分析：第2章算法分析基础.ppt