算法导论学习笔记(一)

Posted by HK on January 31, 2019

第一章 介绍算法的定义,以及相对于计算机中使用的其他技术来说算法的作用。

第二章 介绍一个贯穿本书的框架

第一章 算法在计算中的作用

算法

算法:任何两良定义的计算过程。该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。即算法为输入转换成输出的计算步骤的一个序列。

实例 instance。问题实例由计算该问题解所必需的(满足问题陈诉中强加的各种约束的)输入组成。

算法正确:对每个输入实例,算法都以正确的输出停机。

数据结构:一种存储和组织数据的方式,旨在便于访问和修改。没有一种单一的数据结构对所有用途有效,重要的是知道几种数据结构的优势和局限。

并行性

第二章 算法基础

插入排序 INSERTION-SORT

其中的参数是一个数组A[1..n],包含长度为n的要排序的一个序列,该算法原址排序输入的数:算法在数组A中重排这些数,在任何时候,最多只有其中的常数个数字存储在数组外面。在过程INSERTION-SORT结束时,输入数组A包含排序好的输出序列。

分析算法

设计算法