<算法导论>学习笔记(1)--第1章算法在计算中的作用

矫情吗；* 2022-08-24 14:09 194阅读 0赞

**<算法导论>学习笔记(1)--第1章 算法在计算中的作用**

Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.

是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。

**1. 算法(algorithm)可以用英语、计算机程序甚至是硬件设计来表达，它是一系列的 计算步骤，用来将输入数据转换成输出结果。简单的说，算法是定义良好的计算过程。**

**2. 算法有正确的，也有不正确的，如果不正确算法的错误率可以得到控制的话，它们有时也是有用的，但一般我们只关注正确的算法。**

**3. 数据结构是存储和组织数据的一种方式，以便对数据迕行访问和修改。没有一种数据结构可以适用于所有用途和目的，因此了解数据结构的长处和局限性相当重要。**

**4. 衡量算法效率的常用标准是速度。**

**5. 算法即是一系列的计算步骤,用来将一个有效的输入转换成一个有效的输出。**

**6. 计算机的有限的资源必须被有效的利用,算法就是来解决这些问题的方法。**

练习

1.1-1　给出现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子。

1.1-2　除速度外，在真实环境中还可能使用哪些其他有关效率的量度？

1.1-3　选择一种你以前已知的数据结构，并讨论其优势和局限。

1.1-4　前面给出的最短路径与旅行商问题有哪些相似之处？又有哪些不同？

1.1-5　提供一个现实生活的问题，其中只有最佳解才行。然后提供一个问题，其中近似最佳的一个解也足够好。

【练习答案】

1.1-1:给出现实生活中需要排序的一个例子

a)排序:将一次考试中 500名考生的成绩按分数从高到低迕行排名。  
b)确定多矩阵相乘的最佳顺序:某实验模型,需要计算 返 17个矩阵的积,根据矩阵乘法的结合律确定计算顺序,以达到计算乘法次数最少的目的。※矩阵乘法的结合律:  
c)找出凸壳:木板上钉了 21个钉子,以其中一些钉子为顶点组成的凸多边形可以包含所有 21个钉子,找出使凸多边形达到最小的所有钉子。

1.1-2:  
占用资源大小,问题的解决程度,答案精度等。

1.1-3:

栈(LIFO):长处是可以严格按照后迕先出顺序,非常适合如保存程序调用的迒回地址之类的特殊应用,缺点是无法迕行随机读写。

1.1-4:  
相似之处:都是寻求最短的路线

不同之处:最短路线问题是从若干条可选线路中选择一条线路使之在两个点之间达到

**学习的路上，与君共勉。**

发表评论取消回复

表情：

评论列表（有 0 条评论，194人围观）

还没有评论，来说两句吧...

相关阅读

相关算法导论学习笔记第七章快速排序

快排最坏时间复杂度为θ（n²），但它的平均性能很好，通常是实际排序应用中最好的选择，它的期望时间复杂度为θ（nlgn），且θ（nlgn）中隐含的常数因子非常小，且它还能进行原址

青旅半醒/ 2023年01月14日 01:45/ 0 赞/ 172 阅读

相关算法导论学习笔记第六章堆排序

实际中，待排序的数很少是单独的数值，它们通常是称为记录的数据集的一部分，每个记录包含一个关键字，即排序问题中要重排的值，记录的剩余部分由卫星数据组成，通常是要与关键字一同存取的

约定不等于承诺〃/ 2022年11月18日 08:05/ 0 赞/ 220 阅读

相关算法导论学习笔记第四章分治策略

分治策略中，我们递归地求解一个问题，每层递归中应用如下三个步骤： 1.分解。将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。 2.解决。递归地求解出子问

逃离我推掉我的手/ 2022年11月10日 14:26/ 0 赞/ 265 阅读

相关算法导论学习笔记第二章算法基础

使用插入排序解决以下排序问题：输入：n个数的一个序列<a1, a2, … , an>。输出：输入序列的一个排列<a1’, a2’, …, an’>，满足a1’<=a

蔚落/ 2022年11月06日 00:59/ 0 赞/ 272 阅读

相关算法导论学习笔记第一章算法在计算中的作用

非形式地说，算法是任何良定义（指无歧义的、不会导致矛盾的、符合其应满足的所有要求的定义）的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。算法就是把输

╰半夏微凉°/ 2022年11月05日 11:59/ 0 赞/ 6 阅读

相关 <算法导论>学习笔记(2)--第2章算法基础

<算法导论>学习笔记(2)--第2章算法基础 Having a solid base of algorithm knowledge and technique is one

心已赠人/ 2022年08月24日 14:09/ 0 赞/ 577 阅读

相关 <算法导论>学习笔记(1)--第1章算法在计算中的作用

<算法导论>学习笔记(1)--第1章算法在计算中的作用 Having a solid base of algorithm knowledge and technique i

矫情吗；*/ 2022年08月24日 14:09/ 0 赞/ 195 阅读

相关算法导论 1.1-1

说明INSERTION-SORT在数组A=<31，41，59，26， 41，58>上的执行过程 int[] A = { 31,41,59,26,41,58 };

小鱼儿/ 2022年06月06日 11:38/ 0 赞/ 260 阅读

相关算法导论1.1

说明INSERTION-SORT在数组A=<31，41，59，26， 41，58>上的执行过程 int[] A = { 5, 2, 4, 6, 1, 3 };

骑猪看日落/ 2022年06月06日 11:28/ 0 赞/ 288 阅读

相关算法导论——基础-算法在计算中的作用

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

灰太狼/ 2021年07月25日 23:43/ 0 赞/ 448 阅读