算法艺术与信息学竞赛 (豆瓣)

作者: 刘汝佳
出版社: 清华大学出版社
出版年: 2004-1
页数: 428
定价: 45.00元
装帧: 简裝本
ISBN: 9787302078005

8.5

(487人评价)

43.1%

42.1%

13.6%

0.2%

1.0%

想读在读读过

评价:

内容简介 · · · · · ·

　　《算法艺术与信息学竞赛》较为系统和全面地介绍了算法学最基本的知识。这些知识和技巧既是高等院校“算法与数据结构”课程的主要内容，也是国际青少年信息学奥林匹克（IOI）竞赛和ACM/ICPC国际大学生程序设计竞赛中所需要的。书中分析了相当数量的问题。
　　本书共3章。第1章介绍算法与数据结构；第2章介绍数学知识和方法；第3章介绍计算机几何。全书内容丰富，分析透彻，启发性强，既适合读者自学，也适合于课堂讲授。
　　本书适用于各个层次的信息学爱好者、参赛选手、辅导老师和高等院校计算机专业的师生。本书既是信息学入门和提高的好帮手，也是一本内容丰富、新颖的资料集。

豆瓣成员常用的标签(共83个) · · · · · ·

算法(256) ACM(147) 计算机(76) 信息学(67) 编程(59) 算法艺术与信息学竞赛(55) OI(54) algorithm(46)

喜欢读"算法艺术与信息学竞赛"的人也喜欢 · · · · · ·

: 算法导论

: 组合数学

: 挑战编程

: 具体数学

: 算法导论

: 组合数学

: 世界大学生程序设计竞赛

: 算法竞赛入门经典

: 实用算法的分析与程序设计

: C++ Primer中文版

读书笔记 · · · · · · (共2篇)
我来写笔记

按有用程度 按页码先后 最新笔记

第1页

Dimelo

个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟对于编程能力的提高也没有想象中的高看得出来作者都是竞赛和学术的大牛型人物，但是多数地方没有讲的非常清楚。（个人智商低，理解起来有些费力呀~）本书作为题库，还是非常不错的另外。。。。。。排版太糟糕了 (更多)

个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟
对于编程能力的提高也没有想象中的高
看得出来作者都是竞赛和学术的大牛型人物，但是多数地方没有讲的非常清楚。（个人智商低，理解起来有些费力呀~）
本书作为题库，还是非常不错的
另外。。。。。。排版太糟糕了 (收起)

2011-08-31 09:43:58 回应

收藏
推荐
第2页

xx (披星戴月)
1.1 编程的灵魂——数据结构+算法 = 程序算法（algorithm）就是解决问题的方法或者过程。数据结构（data structure）是数据的计算机表示和相应的一组操作。时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。程序一： /代码内容已省略/ 共执行了n个基本操作；程序二： (更多)
1.1 编程的灵魂——数据结构+算法 = 程序
算法（algorithm）就是解决问题的方法或者过程。
数据结构（data structure）是数据的计算机表示和相应的一组操作。
时空开销增长
- 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。
- 只关心在问题规模扩大时时空开销的增长情况。
程序一：
```
fact = 1;
for (int i = 1;i <= n; i++)
    fact *= i;
```
共执行了n个基本操作；
程序二：
```
sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum += a[i][j];
```
执行了n^2个基本操作；
程序一的渐进时间复杂度低，因此更优。
复杂度分析的常用符号
- 若存在两个正常数c和n0，对任意的 n > n0 都有 |T(n)|<=c|f(n)|，则称T(n)在集合O(f(n))中。记作T(n) = O(f(n))。
- T(n)的增长速度不会比f(n)差。
- 大O表示法（big-Oh notation）表示的是运行时间的上限。
- 小o表示法,表示这个上限是“松”的。
简化法则
- 简化的方法是忽略常数和低次项，如 3n^4 + 8n^2 + n + 2 = O(n^4)
复杂度的等级
- 多项式算法
- 它的运行时间随着规模的扩大增长不大，因此叫做有效算法；
- 指数级算法
- 运行时间增长很快，不是有效算法。
- 包含 Ackermann 函数反函数的算法往往代表着算法使用了并查集或者利用了某函数的凹凸性
- 含 logn 的往往是用了递归、二分或者操作时间复杂度表达式含 logn 的数据结构
- n^(1/2) 或者用更“奇怪”的常数a作为指数的 O(n^a) 类算法的往往是多级算法（如二级检索），分阶段算法（如二分图匹配的 Hopcroft 算法），或者待定参数的算法。a是最后解出的最优参数。
时空辩证关系
- 时间换空间
- 常用方法是重复计算
- 空间换时间
- 常用方法是预处理
P类问题和NP问题
- 如果一个问题可以在多项式时间内被确定机解决，则它属于 P 类问题
- 如果它可以在多项式时间内被非确定机解决，则它属于 NP 类问题
NP完全（NPC）问题
- 满足：
- 属于NP
- NP 中的每个问题都可以使用多项式归约到它
Monte-Carlo算法、RP类问题
- 如果一个问题存在一个随机算法，使得它有50%以上的概率得到期望的结果，那么这个问题属于RP类，该算法称为 Monte-Carlo (收起)
2011-02-01 13:42:26 1回应

收藏
推荐

第1页

Dimelo

个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟对于编程能力的提高也没有想象中的高看得出来作者都是竞赛和学术的大牛型人物，但是多数地方没有讲的非常清楚。（个人智商低，理解起来有些费力呀~）本书作为题库，还是非常不错的另外。。。。。。排版太糟糕了 (更多)

个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟
对于编程能力的提高也没有想象中的高
看得出来作者都是竞赛和学术的大牛型人物，但是多数地方没有讲的非常清楚。（个人智商低，理解起来有些费力呀~）
本书作为题库，还是非常不错的
另外。。。。。。排版太糟糕了 (收起)

2011-08-31 09:43:58 回应

收藏
推荐
第2页

xx (披星戴月)
1.1 编程的灵魂——数据结构+算法 = 程序算法（algorithm）就是解决问题的方法或者过程。数据结构（data structure）是数据的计算机表示和相应的一组操作。时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。程序一： /代码内容已省略/ 共执行了n个基本操作；程序二： (更多)
1.1 编程的灵魂——数据结构+算法 = 程序
算法（algorithm）就是解决问题的方法或者过程。
数据结构（data structure）是数据的计算机表示和相应的一组操作。
时空开销增长
- 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。
- 只关心在问题规模扩大时时空开销的增长情况。
程序一：
```
fact = 1;
for (int i = 1;i <= n; i++)
    fact *= i;
```
共执行了n个基本操作；
程序二：
```
sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum += a[i][j];
```
执行了n^2个基本操作；
程序一的渐进时间复杂度低，因此更优。
复杂度分析的常用符号
- 若存在两个正常数c和n0，对任意的 n > n0 都有 |T(n)|<=c|f(n)|，则称T(n)在集合O(f(n))中。记作T(n) = O(f(n))。
- T(n)的增长速度不会比f(n)差。
- 大O表示法（big-Oh notation）表示的是运行时间的上限。
- 小o表示法,表示这个上限是“松”的。
简化法则
- 简化的方法是忽略常数和低次项，如 3n^4 + 8n^2 + n + 2 = O(n^4)
复杂度的等级
- 多项式算法
- 它的运行时间随着规模的扩大增长不大，因此叫做有效算法；
- 指数级算法
- 运行时间增长很快，不是有效算法。
- 包含 Ackermann 函数反函数的算法往往代表着算法使用了并查集或者利用了某函数的凹凸性
- 含 logn 的往往是用了递归、二分或者操作时间复杂度表达式含 logn 的数据结构
- n^(1/2) 或者用更“奇怪”的常数a作为指数的 O(n^a) 类算法的往往是多级算法（如二级检索），分阶段算法（如二分图匹配的 Hopcroft 算法），或者待定参数的算法。a是最后解出的最优参数。
时空辩证关系
- 时间换空间
- 常用方法是重复计算
- 空间换时间
- 常用方法是预处理
P类问题和NP问题
- 如果一个问题可以在多项式时间内被确定机解决，则它属于 P 类问题
- 如果它可以在多项式时间内被非确定机解决，则它属于 NP 类问题
NP完全（NPC）问题
- 满足：
- 属于NP
- NP 中的每个问题都可以使用多项式归约到它
Monte-Carlo算法、RP类问题
- 如果一个问题存在一个随机算法，使得它有50%以上的概率得到期望的结果，那么这个问题属于RP类，该算法称为 Monte-Carlo (收起)
2011-02-01 13:42:26 1回应

收藏
推荐

第1页

Dimelo

个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟对于编程能力的提高也没有想象中的高看得出来作者都是竞赛和学术的大牛型人物，但是多数地方没有讲的非常清楚。（个人智商低，理解起来有些费力呀~）本书作为题库，还是非常不错的另外。。。。。。排版太糟糕了 (更多)

个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟
对于编程能力的提高也没有想象中的高
看得出来作者都是竞赛和学术的大牛型人物，但是多数地方没有讲的非常清楚。（个人智商低，理解起来有些费力呀~）
本书作为题库，还是非常不错的
另外。。。。。。排版太糟糕了 (收起)

2011-08-31 09:43:58 回应

收藏
推荐
第2页

xx (披星戴月)
1.1 编程的灵魂——数据结构+算法 = 程序算法（algorithm）就是解决问题的方法或者过程。数据结构（data structure）是数据的计算机表示和相应的一组操作。时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。程序一： /代码内容已省略/ 共执行了n个基本操作；程序二： (更多)
1.1 编程的灵魂——数据结构+算法 = 程序
算法（algorithm）就是解决问题的方法或者过程。
数据结构（data structure）是数据的计算机表示和相应的一组操作。
时空开销增长
- 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。
- 只关心在问题规模扩大时时空开销的增长情况。
程序一：
```
fact = 1;
for (int i = 1;i <= n; i++)
    fact *= i;
```
共执行了n个基本操作；
程序二：
```
sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum += a[i][j];
```
执行了n^2个基本操作；
程序一的渐进时间复杂度低，因此更优。
复杂度分析的常用符号
- 若存在两个正常数c和n0，对任意的 n > n0 都有 |T(n)|<=c|f(n)|，则称T(n)在集合O(f(n))中。记作T(n) = O(f(n))。
- T(n)的增长速度不会比f(n)差。
- 大O表示法（big-Oh notation）表示的是运行时间的上限。
- 小o表示法,表示这个上限是“松”的。
简化法则
- 简化的方法是忽略常数和低次项，如 3n^4 + 8n^2 + n + 2 = O(n^4)
复杂度的等级
- 多项式算法
- 它的运行时间随着规模的扩大增长不大，因此叫做有效算法；
- 指数级算法
- 运行时间增长很快，不是有效算法。
- 包含 Ackermann 函数反函数的算法往往代表着算法使用了并查集或者利用了某函数的凹凸性
- 含 logn 的往往是用了递归、二分或者操作时间复杂度表达式含 logn 的数据结构
- n^(1/2) 或者用更“奇怪”的常数a作为指数的 O(n^a) 类算法的往往是多级算法（如二级检索），分阶段算法（如二分图匹配的 Hopcroft 算法），或者待定参数的算法。a是最后解出的最优参数。
时空辩证关系
- 时间换空间
- 常用方法是重复计算
- 空间换时间
- 常用方法是预处理
P类问题和NP问题
- 如果一个问题可以在多项式时间内被确定机解决，则它属于 P 类问题
- 如果它可以在多项式时间内被非确定机解决，则它属于 NP 类问题
NP完全（NPC）问题
- 满足：
- 属于NP
- NP 中的每个问题都可以使用多项式归约到它
Monte-Carlo算法、RP类问题
- 如果一个问题存在一个随机算法，使得它有50%以上的概率得到期望的结果，那么这个问题属于RP类，该算法称为 Monte-Carlo (收起)
2011-02-01 13:42:26 1回应

收藏
推荐

> 更多读书笔记（共2篇）

书评 · · · · · · 我来评论这本书

"算法艺术与信息学竞赛"的论坛 · · · · · ·


这本书的资料还算比较全……	来自麦圆(麥圓)	1 回应	2009-01-12
ACM Fighting~	来自star	1 回应	2009-01-12
非常好的书	来自wangyk		2010-10-31
微言大义	来自absolute		2009-08-10
当年还没有上市的时候，lrj 签名送的一本	来自雨寒月	3 回应	2010-08-07