Felomeng算法导论(第二版)学习笔记Chapter1

时间:2021-05-01 21:34:33

Algorithm: Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

instance of a problem :In general, an instance of a problem consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.

correct: An algorithm is said to be correct if, for every input instance, it halts with the correct output.

NPC: Nondeterministic Polynomial Complete